1

3

1

Федеральное государственное бюджетное образовательное учреждение

высшего профессионального образования

«Калининградский государственный технический университет»

О.М. Топоркова

ИНФОРМАТИКА

Допущено (рекомендовано) ученым советом ФГБОУ ВПО «КГТУ»

в качестве учебного пособия для студентов высших учебных заведений,

обучающихся в бакалавриате по направлениям подготовки:

«Информатика и вычислительная техника»;

«Прикладная информатика»

Калининград

Издательство ФГБОУ ВПО «КГТУ»

2014



УДК 004(075)

Рецензенты:

доцент, кандидат технических наук В.В. Капустин

доцент, кандидат педагогических наук Н.Б. Розен

Топоркова О.М.

Информатика: учебное пособие/ О.М. Топоркова. - Калининград: Издательство ФГБОУ ВПО «КГТУ», 2014. - 91 с.

Изложены основные понятия информатики, существенные для ее начального изучения: системы счисления и правила выполнения простейших арифметических операций в них, правила перевода чисел между различными системами счисления, кодирование дискретного сигнала, измерение информации, структурные основные элементы компьютера и их взаимодействие в процессе функционирования.

Учебное пособие предназначено для студентов вузов, обучающихся по направлениям подготовки: Информатика и вычислительная техника; Прикладная информатика.

Ил. 15, табл. 37, список лит. - 6 наименований

Кафедра систем управления и вычислительной техники

Учебное пособие рекомендовано к изданию методической комиссией факультета автоматизации производства и управления 17.02.2014, протокол № 2.

УДК 004(075)

	© Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования «Калининградский государственный технический университет»



Оглавление

• ВВЕДЕНИЕ 5
• 1. Основные понятия информатики и информации 6
• 1.1. Информатизация общества 6
• 1.2. Понятие информатики 7
• 1.3. Понятие и характерные черты информации 8
• 1.4. Классификация информации 10
• 1.5. Свойства информации 11
• 2. Кодирование информации 13
• 2.1. Виды сигнала как материального носителя информации 13
• 2.2. Преобразования сигнала 14
• 2.3. Системы счисления 15
• 2.4. Правила перевода чисел 17
• 2.4.1. Правила перевода целых чисел 17
• 2.4.2. Правила перевода правильных дробей 19
• 2.4.3. Правило перевода неправильных дробей 22
• 2.5. Правила выполнения простейших арифметических действий 22
• 2.6. Кодирование дискретного сигнала 23
• 2.7. Кодирование по образцу 24
• 2.7.1. Прямые коды 25
• 2.7.2. ASCII-коды 26
• 2.7.3. Коды, учитывающие частоту информационных элементов 28
• 2.7.4. Коды Грея 30
• 2.8. Криптографическое кодирование 31
• 2.8.1. Метод простой подстановки 31
• 2.8.2. Метод Виженера 33
• 2.9. Эффективное кодирование 36
• 2.9.1. Универсальные методы 36
• 2.9.1.1. Метод Шеннона-Фано 36
• 2.9.1.2. Метод Хаффмена 39
• 2.9.1.3. Повышение эффективности кодирования 40
• 2.9.1.4. Декодирование универсальных эффективных кодов 41
• 2.9.2. Специальные методы эффективного кодирования 42
• 2.9.2.1. Методы эффективного кодирования числовых последовательностей 42
• 2.9.2.2. Методы эффективного кодирования словарей 44
• 2.9.2.3. Методы эффективного кодирования естественно-языковых текстов 45
• 2.10. Помехозащитное кодирование 46
• 2.10.1. Искажение кодовых комбинаций 46
• 2.10.2. Кодовое расстояние и корректирующая способность кода 47
• 2.10.3. Коды, исправляющие ошибки 50
• 3. Измерение информации 54
• 3.1. Структурный подход к измерению информации 54
• 3.1.1. Геометрическая мера 54
• 3.1.2. Комбинаторная мера 55
• 3.1.3. Аддитивная мера 56
• 3.2. Статистический подход к измерению информации 57
• 3.3. Семантический подход к измерению информации 59
• 3.3.1. Целесообразность информации 59
• 3.3.2. Полезность информации 59
• 3.3.3. Истинность информации 60
• 3.4. Качество информации 61
• 4. Технические средства информатики 63
• 4.1. Структура компьютера и принципы его функционирования 63
• 4.2. Виды современных компьютеров 65
• 4.3. Структурные элементы компьютера 66
• 4.3.1. Память 68
• 4.3.1.1. Внутренняя память 69
• 4.3.1.2. Внешняя память 71
• 4.3.2. Устройство управления 77
• 4.3.3. Арифметико-логическое устройство 78
• 4.3.3.1. Формы представления целых чисел 79
• 4.3.3.2. Формы представления вещественных чисел 79
• 4.3.3.3. Коды представления числовых данных 81
• 4.3.3.4. Принципы выполнения арифметической операции сложения 82
• ЛИТЕРАТУРА 89
• ПРИЛОЖЕНИЕ 1. Положения комбинаторики, используемые в измерении информации 90


ВВЕДЕНИЕ

Понятие информатики является относительно новым в лексиконе современного человека. Несмотря на повсеместное употребление, его содержание остается не проясненным до конца в силу своей новизны. Интуитивно ясно, что оно связано с информацией, а также с ее обработкой на компьютерах. Это подтверждается существующей легендой о происхождении данного слова: считается, что оно составлено из двух слов - ИНФОРмация и автоМАТИКА (как наука, изучающая автоматы, в частности, для преобразования информации).

Вследствие широкого распространения компьютеров и информационного бума, который переживает человечество, с азами информатики должен быть знаком всякий грамотный современный человек; вот почему ее преподавание включено в курс средней школы и продолжается в высшей школе.

Данное учебное пособие раскрывает понятие информатики через основополагающие компоненты - информацию и компьютер - и состоит из четырех частей.

В первой части определяются понятия информатики, информационного общества, информации.

Во второй части вводится понятие сигнала как материального носителя информации, описываются виды и преобразования сигнала. Рассматриваются способы кодирования дискретного сигнала, принятые в информатике для решения различных прикладных задач. Поскольку при кодировании используются различные системы счисления, приводятся те их них, которые применимы в современной информатике, даются правила перевода из одной системы счисления в другую, разбираются правила сложения в двоичной системе счисления.

В третьей части рассматриваются различные подходы к измерению информации и к оценке ее качества.

В четвертой части приводится структура компьютера и принципы функционирования ЭВМ, заложенные в проекте Принстонской машины, рассматриваются элементы структурной схемы компьютера и принципы их функционирования.

1. Основные понятия информатики и информации

1.1. Информатизация общества

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

Под информатизацией общества понимают организованный социально-экономический и научно-технический процесс создания оптимальных условий для удовлетворения информационных потребностей и реализации прав физических и юридических лиц на основе формирования и использования информационных ресурсов - данных и знаний в различной форме представления.

Целью информатизации является создание информационного общества, когда большинство людей занято производством, хранением, переработкой и реализацией информации. Для решения этой задачи возникают новые направления в научной и практической деятельности членов общества. Так возникли информатика и информационные технологии.

Характерные черты информационного общества:

решена проблема информационного кризиса, когда устранено противоречие между информационной лавиной и информационным голодом;

обеспечен приоритет информации перед другими ресурсами;

главной формой развития общества является информационная экономика;

в основу общества закладывается автоматизированная генерация, хранение, обработка и использование знаний с помощью новейшей информационной техники и технологии;

информационные технологии приобретают глобальный характер, охватывая все сферы социальной деятельности человека;

формируется информационное единство всей человеческой цивилизации;

с помощью средств информатики реализован свободный доступ каждого человека к информационным ресурсам всей цивилизации;

реализованы гуманистические принципы управления обществом и воздействия на окружающую среду.

Возможны и негативные тенденции, сопровождающие процесс информатизации общества:

все большее влияние приобретают средства массовой информации;

информационные технологии могут разрушить частную жизнь человека;

существенное значение приобретает проблема качественного отбора достоверной информации;

некоторые люди испытывают сложности адаптации к информационному обществу.

В настоящий момент ближе всех к информационному обществу находятся США, Япония, Англия, страны Западной Европы.

1.2. Понятие информатики

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

Информатика - область человеческой деятельности, связанная с процессами преобразования информации с помощью компьютеров и других средств вычислительной техники. Более конкретно с информатикой связывают одно из следующих понятий или их комбинацию:

1) информатика - это совокупность средств (технических, программных, интеллектуальных) преобразования информации:

· в состав технических (аппаратных) средств (hardware) входят компьютеры и связанные с ними периферийные устройства (мониторы, клавиатуры, принтеры и плоттеры, модемы и т.д.), линии связи, средства оргтехники и т.п., т.е. те материальные ресурсы, которые обеспечивают преобразование информации, причем главенствующую роль в этом списке играет компьютер. По своей специфике компьютер нацелен на решение очень широкого круга задач по преобразованию информации, при этом выбор конкретной задачи при использовании компьютера определяется программным средством, под управлением которого функционирует компьютер;

· к программным средствам (продуктам) (software) относятся операционные системы, интегрированные операционные оболочки, системы программирования и проектирования программных продуктов, различные прикладные пакеты, такие, как текстовые и графические редакторы, бухгалтерские и издательские системы и т.д. Конкретное применение каждого программного продукта специфично и служит для решения определенного круга задач прикладного или системного характера;

· интеллектуальные средства информатики (brainware) соответствуют математическим методам, моделям и типовым алгоритмам, которые являются базисом, положенным в основу проектирования и изготовления любого программного или технического средства в силу их исключительной сложности и, как следствие, невозможности умозрительного подхода к созданию.

Перечисленные выше три ресурсных компонента информатики играют разную роль в процессе информатизации общества. Так, совокупность программных и технических средств, имеющихся в том или ином обществе, позволяет сделать его информационным, когда каждый член общества имеет возможность получить практически любую (исключая, естественно, секретную) интересующую его информацию (такие потребители информации называются конечными пользователями). В то же время, сложность технических и программных систем заставляет использовать имеющиеся технические и программные продукты, а также нужные методы, модели и алгоритмы для проектирования и производства новых и совершенствования старых технических и программных систем. В этом случае можно сказать, что средства преобразования информации используются для производства себе подобных. Тогда их пользователем является специалист в области информатики и информационных технологий, а не конечный пользователь;

2) информатика - это отрасли производства для создания технических и программных средств. Наиболее известными фирмами для изготовления технических средств информатики являются IBM, Apple, Intel, Hewlett Packard, для производства программных продуктов - Microsoft, Lotus, Borland;

3) информатика - это фундаментальная наука, которая занимается разработкой методов, моделей и алгоритмов преобразования информации, т.е. созданием brainware. Ее прерогативой является исследование процессов преобразования информации и на основе этих исследований разработка соответствующих теорий, моделей, методов и алгоритмов, которые затем применяются на практике;

4) информатика - это прикладная наука, позволяющая путем объединения технических, программных и интеллектуальных средств автоматизировать конкретные информационные процессы в той или иной предметной области, т.е. создавать информационные технологии.

Таким образом, главная функция информатики состоит в разработке методов и средств преобразования информации с использованием компьютера и в применении их при организации технологического процесса преобразования информации.

Выполняя свою функцию, информатика решает следующие задачи:

исследует информационные процессы в различных системах;

разрабатывает информационную технику и создает новейшие технологии преобразования информации на основе результатов, полученных в ходе исследования информационных процессов;

решает научные и инженерные проблемы создания, внедрения и обеспечения эффективного использования компьютерной техники и технологии во всех сферах человеческой деятельности.

1.3. Понятие и характерные черты информации

Как видно из определения информатики, ее функций и задач, приведенных выше, одним из ключевых понятий информатики является информация.

Информация - это сведения об окружающем мире (объекте, процессе, явлении, событии и т.д.), которые являются объектом преобразования (включая хранение, передачу и т.д.) и используются для принятия решения.

Мы постоянно пользуемся информацией. Например, выходя утром из дома, мы слушаем по радио прогноз погоды на день и принимаем решение о том, понадобится ли нам зонт. В этом случае информация, содержащаяся в прогнозе, влияет на наше решение, которое рождается в недрах собственного сознания, например, в форме фразы: «возьму-ка я зонтик, поскольку давление понижается». Так же и преподаватель использует ответ студента на экзамене в качестве информации, которая позволяет принять решение об оценке.

Характерные черты информации:

1. Это наиболее важный ресурс современного производства: он снижает потребность в земле, труде, капитале, уменьшает расход сырья и энергии. Примером является применяемая в сельском хозяйстве агротехника выращивания овощных культур без привлечения земельных ресурсов - гидропоника, которая использует вместо земли растворы, насыщенные полезными для растений веществами. Здесь потребность в земле снижается до нуля. Таким образом, владея подобной технологией, т.е. обладая соответствующей информацией, можно выращивать овощные культуры.

2. Информация вызывает к жизни новые производства. Так, изобретенный в первой половине 20-го века лазерный луч (в 1964 году ученые Ч. Таунс, Н.Г. Басов и А.М. Прохоров получили Нобелевскую премию по физике за это изобретение) послужил началу развития лазерной связи.

3. Информация является товаром, который остается у продавца после продажи, что делает информацию очень выгодным товаром, поскольку одну и ту же информацию можно многократно продавать.

4. Информация придает дополнительную ценность другим ресурсам. Действительно, работник с высшим образованием ценится больше, чем со средним. Автомобиль последней модели, в котором воплощены научно-технические разработки ученых и инженеров, т.е. новая информация, более дорогой, чем его предшественники.

5. Информация может накапливаться. Речь идет не о простом количественном пополнении объемов информации, а о формировании новых знаний, что позволяет развивать общество, поскольку владея определенными знаниями, человек может генерировать новую информацию. Именно таким образом учеными совершаются открытия в области науки, инженерами создаются новые технические изобретения. Чем больше знает человек и чем качественнее эти знания, тем большее количество новой информации он может сформировать.

Как следует из определения, с информацией связаны три понятия (их взаимосвязь показана на рис. 1.1):

источник информации - элемент окружающего мира, сведения о котором являются объектом преобразования;

потребитель информации - элемент окружающего мира, который использует информацию для принятия решения;

сигнал - материальный носитель, который фиксирует информацию для переноса ее от источника к потребителю.

Рис. 1.1. Схема взаимосвязи основных понятий информации

Так, источником информации, которую в данный момент получает читатель настоящего учебного материала, является информатика как сфера человеческой деятельности; потребителем - сам читатель, а сигналом - текст на электронном (или бумажном) носителе. Будучи прочитанной и запомненной студентом, данная информация приобретет еще один носитель - биологический, когда она «записывается» в память обучаемого. Очевидно, что источник и потребитель в этом случае не меняются.

Уже отмечалось, что информационный ресурс существует в виде данных и знаний: данные - это полученные путем наблюдения и зафиксированные факты, дискретно, т.е. через отдельные свойства, описывающие источник информации (говорят - предметную область (ПО)); знания - это закономерности источника информации (понятия, сведения, принципы, связи, законы), приобретенные в результате практической деятельности; они позволяют специалистам ставить и решать задачи в этой предметной области.

Примером данных могут служить сведения о результатах сдачи сессии студентами и о последующих решениях деканата - это некоторый набор фактов. Например, студент Х имеет двойку по дисциплине Y; студента Х отчисляют из вуза.

Если на основании множества фактов делается обобщение следующего вида: каждый студент, не сдавший экзамен, т.е. имеющий двойку, отчисляется из вуза, то это уже выявленная закономерность, т.е. знание.

1.4. Классификация информации

Классификацию информации выполняют по нескольким основаниям (эта классификация не является строгой и может меняться):

1. По времени возникновения:

а) априорная - известна потребителю заранее, до получения сигнала;

б) апостериорная - становится известной потребителю после получения сигнала.

Получаемая сейчас читателем информация является априорной, т.е. уже известной, если он освоил азы информатики в школе, и апостериорной, т.е. новой, в противном случае.

2. По стабильности:

а) переменная - отражает фактические характеристики источника информации. Может меняться;

б) постоянная - неизменная и многократно используемая в течение длительного периода времени. Строго говоря, и эта информация может меняться, но с гораздо меньшей частотой, которой можно пренебречь.

В настоящем учебном пособии используются оба вида информации. Упомянутые выше фирмы-производители технических и программных средств относятся к первому виду. В самом деле, может быть, что к моменту прочтения данного текста эти фирмы перестанут существовать на рынке производителей. В то же время весь понятийный аппарат, излагаемый по тексту, относится к постоянной информации и является тем базисом, который позволяет информатикам говорить на одном профессиональном языке.

3. По способу использования:

а) открытая - ее использование ничем не ограничено;

б) закрытая - ее использование возможно с согласия определенных физических или юридических лиц;

в) коммерческая - является объектом купли-продажи.

Отметим в качестве комментария, что излагаемая в учебном пособии информация не является ни закрытой, ни коммерческой - она находится в открытом доступе для всех желающих.

1.5. Свойства информации

Будучи объектом преобразования и использования, информация, зафиксированная в сигнале, характеризуется следующими свойствами:

синтаксис - свойство, определяющее способ представления информации на носителе (в сигнале). Данная информация представлена на носителе с помощью определенного шрифта. Здесь же можно рассматривать такие параметры представления информации, как стиль и цвет шрифта, его размеры, формат бумаги и ее качество и т.д. Выделение нужных параметров как синтаксических свойств, очевидно, определяется предполагаемым способом преобразования. Например, для плохо видящего человека существенным является размер и цвет шрифта;

семантика - свойство, определяющее смысл информации как соответствие сигнала реальному миру. Семантика сигнала «информатика» заключается в данном ранее определении. Семантика может рассматриваться как некоторое соглашение, известное потребителю информации, о том, что означает каждый сигнал (так называемое правило интерпретации). Например, именно семантику сигналов изучает начинающий автомобилист, штудирующий правила дорожного движения, познавая дорожные знаки (в этом случае сигналами выступают сами знаки). Семантику слов (сигналов) познаёт обучаемый какому-либо иностранному языку. Можно сказать, что смысл настоящего обучения информатике заключается в изучении семантики различных сигналов - суть ключевых понятий этой дисциплины;

прагматика - свойство, определяющее влияние информации на поведение потребителя. Прагматика информации, получаемой читателем настоящего учебного пособия, заключается, по меньшей мере, в успешной сдаче экзамена по информатике. Хочется верить, что этим прагматика данного труда не ограничится, и он послужит для дальнейшего обучения и профессиональной деятельности читателя.

Проецируя приведенные свойства информации на элементы схемы рис. 1.1, можно схему видоизменить следующим образом (рис. 1.2):

Рис. 1.2. Соотношение свойств информации

Синтаксис определяет свойства сигнала как такового, семантика выражает связь сигнала с источником информации, а прагматика представляет влияние сигнала на потребителя информации.

Следует отметить, что различные по синтаксису сигналы могут иметь одинаковую семантику. Например, сигналы «ЭВМ» и «компьютер» означают электронное устройство для преобразования информации. В этом случае обычно говорят о синонимии сигналов.

С другой стороны, один сигнал (т.е. информация с одним синтаксическим свойством) может иметь разную прагматику для потребителей. Дорожный знак, известный под названием «кирпич» и имеющий вполне определенную семантику («въезд запрещен»), означает для автомобилиста запрет на въезд, а на пешехода никак не влияет.

В то же время, сигнал «ключ» может иметь разную семантику: скрипичный ключ, родниковый ключ, ключ для открытия замка или гаечный ключ (в этом случае говорят об омонимии сигнала).



2. Кодирование информации

2.1. Виды сигнала как материального носителя информации

Сигнал, который фиксирует информацию, может быть дискретным и непрерывным (аналоговым).

Дискретный сигнал слагается из счетного множества (т.е. такого множества, элементы которого можно пересчитать) элементов (говорят - информационных элементов). Например, дискретным является сигнал «кирпич» (см. выше). Он состоит из следующих двух элементов (это синтаксическая характеристика данного сигнала): красного круга и белого прямоугольника внутри.

Именно в виде дискретного сигнала представлена та информация, которую сейчас осваивает читатель. Можно выделить следующие ее элементы: разделы (например, «Информатизация общества»), подразделы (например, «Виды сигнала»), абзацы, предложения, отдельные фразы, слова и отдельные знаки (буквы, цифры, знаки препинания и т.д.).

Последний пример показывает, что в зависимости от прагматики информации можно выделять разные информационные элементы. В самом деле, для лица, изучающего информатику по данному конспекту, важны более крупные информационные элементы, такие как разделы, подразделы, отдельные абзацы. Они позволяют ему легче ориентироваться в структуре материала, лучше его усваивать и готовиться к экзамену. Для того, кто готовил данный материал, помимо указанных информационных элементов, важны также и более мелкие, например, отдельные предложения, с помощью которых излагается та или иная мысль и которые реализуют тот или иной способ доступности материала. Для издателя важны еще более мелкие детали, например, такие характеристики отдельных символов, как их размер, стиль и т.д., поскольку существуют определенные правила подготовки печатного текста.

Набор самых «мелких» элементов дискретного сигнала называется алфавитом, а сам дискретный сигнал называют также сообщением.

Если в качестве дискретного сигнала рассматривать некоторый текст, то его алфавитом можно считать буквы, знаки препинания и т.д. Если дискретный сигнал - это некоторый набор целых десятичных чисел, то алфавит - это десятичные цифры.

Непрерывный сигнал отражается некоторой физической величиной, изменяющейся в заданном интервале времени. Примерами такого сигнала в окружающем мире могут служить звуки, световые волны.

В виде непрерывного сигнала представлена настоящая информация для тех студентов-потребителей, которые посещают лекции по информатике и через звуковые волны, переносящие голос лектора и носящие непрерывный (между паузами) характер, воспринимают материал.

Современные технические средства информатики связаны, в основном, с преобразованиями дискретного сигнала. По этой причине возникает задача прямого и обратного преобразования аналогового сигнала в дискретный.

2.2. Преобразования сигнала

Для преобразования аналогового сигнала в дискретный используется процедура, которая называется квантованием. Она включает два последовательных этапа: квантование по времени и квантование по уровню (дискретизацию).

Квантование по времени - замена непрерывной (по времени и по уровню) функции x(t) (рис. 2.1а) некоторым множеством непрерывных (по уровню) функций x(t_i) (на рис. 2.1б i={1,2,3,4}).

Рис.2.1. Иллюстрация к квантованию по времени:

а) аналоговый сигнал x(t) до квантования;

б) дискретный (по времени) сигнал x(t) - результат квантования.

Таким образом, на рис. 2.1 сигнал x(t) преобразован в множество сигналов {x(t₁), x(t₂), x(t₃), x(t₄)}: x(t){x(t₁), x(t₂), x(t₃), x(t₄)}.

Очевидно, квантование по времени связано с потерей информации. В самом деле, дискретный по времени сигнал на рис. 2.1б не показывает, как ведет себя исходный сигнал в моменты времени, например, между t₃ и t₄. Иначе говоря, данный шаг квантования связан с некоторой погрешностью , которая зависит от шага квантования t=t_i-t_i-1: при малых значениях шага t число точек замера высоко, и теряется мало информации; очевидно, картина обратная при больших шагах t.

Квантование по времени различается по регулярности отсчетов:

равномерное, когда t постоянно;

неравномерное, когда t переменно, причем этот вид, в свою очередь, делится на подвиды:

адаптивное, когда t меняется автоматически в зависимости от текущего изменения сигнала. Это позволяет увеличивать шаг t, когда изменения сигнала x(t) незначительны, и уменьшать - в противном случае;

программируемое, когда t изменяется оператором или в соответствии с заранее выставленными условиями, например, в фиксированные моменты времени.

Квантование по уровню - преобразование непрерывных (по уровню) сигналов x(t_i) в дискретные (рис. 2.2). Шаг квантования x определяется по формуле: x=x_j-x_j-1. Можно сказать, что квантование по уровню - это измерение сигнала. Для этого введем на оси ординат мерную шкалу и спроецируем на нее сигналы x(t_i) (рис. 2.2б).

Рис. 2.2. Иллюстрация к квантованию по уровню:

а) аналоговые по уровню (но дискретные по времени) сигналы x(t_i) до квантования;

б) квантованные по уровню (измеренные) сигналы x(t_i).

Видно, что сигнал x(t₁) составляет три уровня, сигнал x(t₃) - 6, а x(t₄) - пять уровней квантования. В то же время сигнал x(t₂) попадает в промежуток между четырьмя и пятью и не может быть однозначно измерен. В таком случае поступают одним из следующих способов:

x(t_i) отождествляют с ближайшим значением (в нашем примере - с 4). Тогда в результате процедуры квантования по уровню множество сигналов {x(t₁),x(t₂),x(t₃),x(t₄)}, полученное в первом шаге квантования, преобразуется в множество целых чисел {3,4,6,5}: {x(t₁),x(t₂),x(t₃), x(t₄)}{3,4,6,5};

x(t_i) отождествляют с ближайшим большим значением. Тогда сигнал x(t₂) отождествится с 5 независимо от того, насколько близко он к этому уровню квантования находится. Сформируется множество {3,5,6,5}: {x(t₁),x(t₂),x(t₃), x(t₄)}{3,5,6,5};

x(t_i) отождествляют с ближайшим меньшим значением. Тогда сигнал x(t₂) отождествится с 4. Сформируется множество {3,4,6,5}: {x(t₁),x(t₂),x(t₃),x(t₄)}{3,4,6,5}.

Таким образом, в результате проведения двух последовательных шагов квантования непрерывный сигнал x(t) преобразуется в дискретный сигнал {3,4,6,5} (для первого способа приближения при измерении), который является одномерным массивом для любого языка программирования и с легкостью может быть обработан компьютером.

Очевидно, и при квантовании по уровню возникает погрешность квантования. Она тем меньше, чем меньше шаг квантования.

Виды квантования по уровню:

равномерное, когда диапазон изменения сигнала разбивается на m одинаковых частей,

неравномерное, когда диапазон изменения сигнала разбивается на m различных частей.

2.3. Системы счисления

Для удобства последующего преобразования дискретный сигнал подвергается кодированию. Большинство кодов основано на системах счисления, причем использующих позиционный принцип образования числа, при котором значение каждой цифры зависит от ее положения в числе.

Примером позиционной формы записи чисел является та, которой мы пользуемся (так называемая арабская форма чисел). В числах 123 и 321 значения цифры 3, например, определяются ее положением в числе: в первом случае она обозначает три единицы (т.е. просто три), а во втором - три сотни (т.е. триста).

Тогда полное значение числа получается по формуле (2.1):

где l - количество разрядов числа,

i - порядковый номер разряда,

m - основание системы счисления,

a_i - множитель, принимающий любые целочисленные значения от 0 до m-1 и соответствующий цифре в i-й позиции числа.

Например, для десятичного (m=10) числа 345 его полное значение рассчитывается следующим образом: 3*10²+4*10¹+5*10⁰=345.

Римские числа являются примером полупозиционной системы образования числа: в числах IX и XI знак I обозначает в обоих случаях единицу (признак непозиционной системы), но будучи расположенным слева от знака X (обозначающего десять), вычитается из десяти, а при расположении справа - прибавляется к десяти. В первом случае полное значение числа равно 9, во втором - 11.

В современной информатике используются в основном три системы счисления (все - позиционные): двоичная, шестнадцатеричная и десятичная.

Двоичная система счисления используется для кодирования дискретного сигнала, потребителем которого является вычислительная техника. Такое положение дел сложилось исторически, поскольку двоичный сигнал проще представлять на аппаратном уровне. В этой системе счисления для представления числа применяются два знака - 0 и 1.

Шестнадцатеричная система счисления используется для кодирования дискретного сигнала, потребителем которого является хорошо подготовленный пользователь - специалист в области информатики. В такой форме представляется содержимое любого файла, затребованное через интегрированные оболочки, например, средствами Far. Используемые знаки для представления числа - десятичные цифры от 0 до 9 и буквы латинского алфавита - A, B, C, D, E, F.

Десятичная система счисления используется для кодирования дискретного сигнала, потребителем которого является так называемый конечный пользователь - неспециалист в области информатики (очевидно, что и любой человек может выступать в роли такого потребителя). Используемые знаки для представления числа - цифры от 0 до 9.

Соответствие между первыми несколькими натуральными числами всех трех систем счисления представлено в табл. 2.1.



Таблица 2.1.

Соответствие некоторых целых чисел

Десятичная система	Двоичная система	Шестнадцатеричная система
0	0	0
1	1	1
2	10	2
3	11	3
4	100	4
5	101	5
6	110	6
7	111	7
8	1000	8
9	1001	9
10	1010	A
11	1011	B
12	1100	C
13	1101	D
14	1110	E
15	1111	F
16	10000	10

Для различения систем счисления, в которых представлены числа, в обозначение двоичных и шестнадцатеричных чисел вводят дополнительные реквизиты:

для двоичных чисел - нижний индекс справа от числа в виде цифры 2 или букв В или b (binary - двоичный), либо знак B или b справа от числа. Например, 101000₂ = 101000_b = 101000_B = 101000B = 101000b;

для шестнадцатеричных чисел - нижний индекс справа от числа в виде числа 16 или букв H или h (hexadecimal - шестнадцатеричный), либо знак H или h справа от числа. Например, 3AB₁₆ = 3AB_H = 3AB_h = 3ABH = 3ABh.

Для перевода чисел из одной системы счисления в другую существуют определенные правила.

2.4. Правила перевода чисел

Правила перевода различаются в зависимости от формата числа - целое или правильная дробь. Для вещественных чисел используется комбинация правил перевода для целого числа и правильной дроби.

2.4.1. Правила перевода целых чисел

Результатом перевода целых чисел всегда является целое число.

Разобьем эти правила на три группы:

1. Из десятичной системы счисления - в двоичную или шестнадцатеричную:

а) исходное целое число делится на основание системы счисления, в которую переводится (2 или 16); получается частное и остаток;

б) если полученное частное меньше основания системы счисления, в которую переводится число, процесс умножения прекращается, переходят к шагу в). Иначе над частным выполняют действия, начиная с шага а);

в) все полученные остатки и последнее частное преобразуются в соответствии с табл. 2.1 в цифры той системы счисления, в которую выполняется перевод;

г) формируется результирующее число: его старший разряд - полученное последнее частное, каждый последующий младший разряд образуется из полученных остатков от деления, начиная с последнего и кончая первым. Таким образом, младший разряд полученного числа - первый остаток от деления, а старший - последнее частное.

Пример 2.1. Выполнить перевод числа 19 в двоичную систему счисления:

-19	2
18	-9	2
1	8	-4	2
	1	4	-2	2
		0	2	1
			0

1 0 0 1 1 - результат.

Таким образом, 19=10011₂.

Пример 2.2. Выполнить перевод числа 19 в шестнадцатеричную систему счисления:

-19	16
16	1
3

1 3 - результирующее число.

Таким образом, 19=13₁₆.

Пример 2.3. Выполнить перевод числа 123 в шестнадцатеричную систему счисления:

-123	16
112	7
11

7 В - результирующее число.

Таким образом, 123=7В₁₆.

2. Из двоичной или шестнадцатеричной систем счисления - в десятичную. В этом случае рассчитывается полное значение числа по формуле (2.1).

Пример 2.4. Выполнить перевод числа 13₁₆ в десятичную систему счисления. Имеем:

13₁₆ = 1*16¹ + 3*16⁰ = 16 + 3 = 19.

Таким образом, 13₁₆=19.

Пример 2.5. Выполнить перевод числа 10011₂ в десятичную систему счисления. Имеем:

10011₂ = 1*2⁴ + 0*2³ + 0*2² + 1*2¹ + 1*2⁰ = 16+0+0+2+1 = 19.

Таким образом, 10011₂=19.

3. Из двоичной системы счисления в шестнадцатеричную:

а) исходное число разбивается на тетрады (наборы из четырёх цифр), начиная с младших разрядов. Если количество цифр исходного двоичного числа не кратно 4, оно дополняется слева незначащими нулями до достижения кратности 4;

б) каждая тетрада заменяется соответствующей шестнадцатеричной цифрой в соответствии с табл. 2.1.

Пример 2.6. Выполнить перевод числа 10011₂ в шестнадцатеричную систему счисления.

Поскольку в исходном двоичном числе количество цифр не кратно 4, дополняем его слева незначащими нулями до достижения кратности 4 числа цифр. Имеем:

10011₂ = 00010011₂

первая тетрада - младшая цифра числа

вторая тетрада - старшая цифра числа

В соответствии с табл. 2.1 0011₂=11₂=3₁₆ и 0001₂=1₂=1₁₆. Тогда 10011₂= 13₁₆.

4. Из шестнадцатеричной системы счисления в двоичную:

а) каждая цифра исходного числа заменяется тетрадой двоичных цифр в соответствии с табл. 2.1. Если в таблице двоичное число имеет менее 4 цифр, оно дополняется слева незначащими нулями до тетрады;

б) незначащие нули в результирующем числе отбрасываются.

Пример 2.7. Выполнить перевод числа 13₁₆ в двоичную систему счисления.

По табл. 2.1 имеем: 1₁₆=1₂ и после дополнения незначащими нулями 1₂=0001₂; 3₁₆=11₂ и после дополнения незначащими нулями 11₂=0011₂. Тогда 13₁₆=00010011₂. После удаления незначащих нулей имеем 13₁₆=10011₂.

Таким образом, 13₁₆=10011₂.

2.4.2. Правила перевода правильных дробей

Результатом перевода правильной дроби всегда является правильная дробь. Выделим также три группы правил:

Из десятичной системы счисления - в двоичную или шестнадцатеричную:

а) исходная дробь умножается на основание системы счисления, в которую переводится (2 или 16);

б) в полученном произведении целая часть преобразуется в соответствии с табл. 2.1 в цифру нужной системы счисления и отбрасывается - она является старшей цифрой получаемой дроби;

в) оставшаяся дробная часть вновь умножается на нужное основание системы счисления с последующей обработкой полученного произведения в соответствии с шагом б);

г) процедура умножения продолжается до тех пор, пока не будет получен нулевой результат в дробной части произведения или не будет достигнуто требуемое количество цифр в результате;

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

Пример 2.8. Выполнить перевод числа 0,847 в двоичную систему счисления. Перевод выполнить до четырех значащих цифр после запятой.

Имеем:

*0,847
2
1,694		*0,694
		2
		1,388		*0,388
				2
				0,776		*0,776
						2
						1,552 и т.д.

0,1101 - результирующее число.

В данном примере процедура перевода прервана на четвертом шаге, поскольку получено требуемое число разрядов результата. Очевидно, это привело к потере ряда цифр.

Таким образом, 0,847=0,1101₂.

Пример 2.9. Выполнить перевод числа 0,847 в шестнадцатеричную систему счисления. Перевод выполнить до трех значащих цифр.

*0,847
16
13,552		*0,552
		16
		8,832		*0,832
				16
				13,312 и т.д.

0,D8D - результирующее число.

В данном примере также процедура перевода прервана.

Таким образом, 0,847=0,D8D₁₆.

2. Из двоичной или шестнадцатеричной систем счисления - в десятичную. В этом случае рассчитывается полное значение числа по формуле (2.1), причем коэффициенты a_i принимают десятичное значение в соответствии с табл. 2.1.

Пример 2.10. Выполнить перевод из двоичной системы счисления в десятичную числа 0,1101₂. Имеем:

0,1101₂ = 1*2^-1 + 1*2^-2 + 0*2^-3 +1*2^-4 = 0,5 + 0,25 + 0 + 0,0625 = 0,8125.

Расхождение полученного результата с исходным для получения двоичной дроби числом (см. пример 2.8) вызвано тем, что процедура перевода в двоичную дробь была прервана.

Таким образом, 0,1101₂=0,8125.

Пример 2.11. Выполнить перевод из шестнадцатеричной системы счисления в десятичную числа 0,D8D₁₆. Имеем:

0,D8D₁₆ = 13*16^-1 + 8*16^-2 + 13*16^-3 = 13*0,0625 + 8*0,003906 + 13* 0,000244 = 0,84692.

Расхождение полученного результата с исходным для получения двоичной дроби числом (см. пример 2.9) вызвано тем, что процедура перевода в шестнадцатеричную дробь была прервана.

Таким образом, 0,D8D₁₆=0,84692.

3. Из двоичной системы счисления в шестнадцатеричную:

а) исходная дробь делится на тетрады, начиная с позиции десятичной точки вправо. Если количество цифр дробной части исходного двоичного числа не кратно 4, оно дополняется справа незначащими нулями до достижения кратности 4;

б) каждая тетрада заменяется шестнадцатеричной цифрой в соответствии с табл. 2.1.

Пример 2.12. Выполнить перевод из двоичной системы счисления в шестнадцатеричную числа 0,1101₂. Имеем:

0,1101₂ = 0,1101₂

первая (и единственная) тетрада

В соответствии с табл. 2.1 1101₂=D₁₆.

Таким образом, 0,1101₂=0,D₁₆.

Пример 2.13. Выполнить перевод из двоичной системы счисления в шестнадцатеричную числа 0,0010101₂.

Поскольку количество цифр дробной части не кратно 4, добавим справа незначащий ноль:

0,0010101₂ = 0,00101010₂.

вторая тетрада

первая тетрада

В соответствии с табл. 2.1 0010₂=10₂=2₁₆ и 1010₂=A₁₆. Тогда имеем 0,0010101₂=0,2A₁₆.

4. Из шестнадцатеричной системы счисления в двоичную:

а) каждая цифра исходной дроби заменяется тетрадой двоичных цифр в соответствии с табл. 2.1;

б) незначащие нули отбрасываются.

Пример 2.14. Выполнить перевод из шестнадцатеричной системы счисления в двоичную числа 0,2А₁₆.

По табл. 2.1 имеем 2₁₆=0010₂ и А₁₆=1010₂.

Тогда 0,2А₁₆=0,00101010₂.

Отбросим в результате незначащий ноль и получим окончательный результат.

Таким образом, 0,2А₁₆=0,0010101₂.

2.4.3. Правило перевода неправильных дробей

В результате перевода неправильной дроби всегда получается неправильная дробь.

Отдельно переводится целая часть числа, отдельно - дробная. Результаты складываются.

Пример 2.15. Выполнить перевод из десятичной системы счисления в шестнадцатеричную числа 19,847. Перевод выполнять до трех значащих цифр после запятой.

Представим исходное число как сумму целого числа и правильной дроби: 19,847 = 19 + 0,847.

Как следует из примера 2.2, 19 = 13₁₆; а в соответствии с примером 2.9 0,847=0,D8D₁₆.

Тогда имеем: 19 + 0,847 = 13₁₆ + 0,D8D₁₆ = 13,D8D₁₆.

Таким образом, 19,847=13,D8D₁₆.

2.5. Правила выполнения простейших арифметических действий

Арифметические операции для двоичных и шестнадцатеричных чисел выполняются по тем же правилам, что и для десятичных чисел, которые хорошо знакомы читателю. Рассмотрим выполнение важнейших для информатики операций арифметического сложения и сложения по модулю 2 для двоичных чисел.

Правила арифметического сложения двоичных чисел представлены ниже:

0₂ + 0₂ = 0₂; 0₂ + 1₂ = 1₂; 1₂ + 0₂ = 1₂; 1₂ + 1₂ = 10₂.

Пример 2.16. Сложить числа 1101₂ и 11011₂.

Запишем слагаемые в столбик и пронумеруем разряды, присвоив младшему разряду номер 1:

номера разрядов	5	4	3	2	1
	+	1	1	0	1
	1	1	0	1	1

Процесс образования результата по разрядам описан ниже:

а) разряд 1 формируется следующим образом: 1₂+1₂=10₂; 0 остается в разряде 1, 1 переносится во второй разряд;

б) разряд 2 формируется следующим образом: 0₂+1₂+1₂=10₂, где вторая 1₂ - единица переноса; 0 остается в разряде 2, 1 переносится в третий разряд;

в) третий разряд формируется следующим образом: 1₂+0₂+1₂=10₂, где вторая 1₂ - единица переноса; 0 остается в разряде 3, 1 переносится в разряд 4;

г) четвертый разряд формируется следующим образом: 1₂+1₂+1₂=11₂, где третья 1₂ - единица переноса; 1 остается в разряде 4, 1 переносится в пятый разряд;

д) пятый разряд формируется следующим образом: 1₂+1₂=10₂; где вторая 1₂ - единица переноса; 0 остается в разряде 5, 1 переносится в шестой разряд.

Таким образом:

номера разрядов	6	5	4	3	2	1
		+	1	1	0	1
		1	1	0	1	1
	1	0	1	0	0	0

Проверим результат. Для этого определим полные значения слагаемых и результата:

1101₂ = 1*2³ +1*2² + 0*2¹ + 1*2⁰ = 8 + 4 + 1 = 13;

11011₂ = 1*2⁴ + 1*2³ + 0*2² + 1*2¹ + 1*2⁰ = 16 + 8 + 2 + 1 = 27;

101000₂ = 1*2⁵ + 0*2⁴ + 1*2³ + 0*2² + 0*2¹ + 0*2⁰ = 32 + 8 = 40.

Поскольку 13+27=40, двоичное сложение выполнено верно.

Сложение по модулю - это арифметическое сложение, при котором оговаривается, превышение какого числа (модуля) должно отражаться при сложении, и, кроме того, при таком сложении отсутствует единица переноса в старший разряд. Обозначается операция знаком . Как правило, такому сложению подвергаются числа с одинаковым количеством разрядов.

Правила сложения по модулю 2 приведены ниже:

0₂0₂=0₂; 0₂1₂=1₂; 1₂0₂=1₂; 1₂1₂=0₂.

Анализ результатов показывает, что эту операцию можно рассматривать как операцию сравнения двух двоичных цифр: если они равны - результат нулевой, если различаются, результат равен 1.

Пример 2.17. Сложить по модулю 2 числа 101₂ и 011₂.

Запишем алгебраические слагаемые в столбик:

	1	0	1
	0	1	1
	1	1	0

2.6. Кодирование дискретного сигнала

Кодирование - это представление сигнала в определенной форме, удобной или пригодной для последующего использования сигнала. Говоря строже, это правило, описывающее отображение одного набора знаков в другой набор знаков. Тогда отображаемый набор знаков называется исходным алфавитом, а набор знаков, который используется для отображения, - кодовым алфавитом, или алфавитом для кодирования. При этом кодированию подлежат как отдельные символы исходного алфавита, так и их комбинации. Аналогично для построения кода используются как отдельные символы кодового алфавита, так и их комбинации.

Совокупность символов кодового алфавита, применяемых для кодирования одного символа (или одной комбинации символов) исходного алфавита, называется кодовой комбинацией, или, короче, кодом символа. При этом кодовая комбинация может содержать один символ кодового алфавита.

Символ (или комбинация символов) исходного алфавита, которому соответствует кодовая комбинация, называется исходным символом.

Совокупность кодовых комбинаций называется кодом.

Взаимосвязь символов (или комбинаций символов, если кодируются не отдельные символы исходного алфавита) исходного алфавита с их кодовыми комбинациями составляет таблицу соответствия (или таблицу кодов).

Следует отметить, что понятие «код» омонимично: оно может употребляться и в смысле кодовой комбинации, и в приведенном выше смысле. Аналогично понятие «кодовая комбинация» синонимично понятию «код».

Кодирование дискретного сигнала выполняется в два этапа:

1) вначале разрабатывается код для заданного исходного алфавита. Этот этап выполняется единожды, и разработанный код применяется многократно для второго этапа,

2) произвольный, предъявленный к кодированию дискретный сигнал собственно кодируется с помощью кодовой таблицы, созданной на этапе 1.

Обратная процедура получения исходных символов по кодам символов называется декодированием. Очевидно, для выполнения правильного декодирования код должен быть однозначным, т.е. одному исходному знаку должна соответствовать точно одна кодовая комбинация и наоборот.

В зависимости от целей кодирования, различают следующие его виды:

кодирование по образцу - используется, в частности, всякий раз для ввода информации в компьютер для ее внутреннего представления, а потому является обязательным видом кодирования;

криптографическое кодирование, или шифрование, - позволяет защитить информацию от несанкционированного доступа;

эффективное, или оптимальное, кодирование - устраняет избыточность данных путем снижения среднего числа символов кодового алфавита для представления одного исходного символа и применяется в архиваторах;

помехозащитное, или помехоустойчивое, кодирование - обеспечивает заданную достоверность в случае, когда на сигнал накладывается помеха, иначе говоря, позволяет обнаруживать и/или исправлять ошибки в кодовых комбинациях.

2.7. Кодирование по образцу

Большинство кодов, используемых в информатике для кодирования по образцу, имеют одинаковую длину и используют двоичную систему для представления кода (и, возможно, шестнадцатеричную как средство промежуточного представления). Рассмотрим несколько видов таких кодов: прямые; ASCII-коды; коды, учитывающие частоту информационных элементов; коды Грея.