Системы счисления. Литература Андреева Е., Фалина И. Системы счисления и компьютерная арифметика. М. Бином. Лаборатория знаний, 2004
 Скачать 215 Kb.
|
|
Системы счисления Задачи по теме кодирования числовой информации (двоичная, восьмеричная и шестнадцатеричная системы счисления) входят в ЕГЭ и ГИА, Литература
Десятичная система Полиномиальное представление Озвучивая запись: 365, мА произносим: «триСТО шестьДЕСЯТ пять», то есть «три сотни, шесть десятков и 5 единиц». Можем считать, что 365 это сокращенная запись 3*100 + 6*10 + 5. Числа 100, 10, 1, которые не пишем в сокращенной записи, называют базой системы счисления. В нашем случае базой является геометрическая прогрессия с начальным значением 1 и знаменателем 10. Из-за знаменателя, эту систему счисления называют десятичной. Пусть имеем некоторое число, например 365. Попытаемся разделить это число на основание системы счисления. Получим ответ 36 и 5 в остатке. Деление на основание системы счисления фактически переносит десятичный знак на одну позицию влево, в остатке получаются значения, для десятичной системы в диапазоне – от 0 до 9. Эти значения называются цифрами и должны обозначаться отдельными одинокими знаками. Мы используем арабские цифры 0123456789. Значение числа получается как результат линейной комбинации цифр числа и соответствующего базового значения. Используя факт, что базой системы счисления является геометрическая прогрессия, можно доказать, что арифметические операции + и * над многозначными числами сводятся к соответствующим операциям над цифрами. Таблицы операций над цифрами заучиваются в младших классах школы. Они нужны для выполнения алгоритмов сложения и умножения «столбиком». На этой же базе реализуются алгоритмы вычитания и деления. Двоичная система Чем число 10 отличается от других чисел? Существенно ничем. Можем взять любое число в качестве знаменателя геометрической прогрессии, и считать эту прогрессию базой системы счисления. Существует самое маленькое целое число, образующее базу – это число 2. Соответственно имеем базу: 1, 2, 4, 8, 16, … Полученная система счисления называется двоичной. Почему? По аналогии с десятичной системой, имеем, что различных цифр достаточно двух. Обозначим их 0 и 1. Операции над многоразрядными числами сводятся к операциям над цифрами. Таблицы операций сложения и вычитания оказываются простыми, легко запоминающимися. Составьте алгоритмы выполнения арифметических операций над многозначными числами в двоичной системе счисления. Проделайте эти операции. Центральное место среди “принципов Неймана — Лебедева”, определяющих фоннеймановскую архитектуру ЭВМ, занимает предложение об использовании двоичной системы счисления. Это предложение было обусловлено рядом обстоятельств: простота выполнения арифметических операций в двоичной системе счисления; ее “оптимальное” согласованием с булевой логикой; простота технической реализации двоичного элемента памяти (триггера). Однако на определенном этапе развития компьютерной техники выявилось, что использование классической двоичной системы счисления для представления информации в компьютере имеет существенные недостатки, влияющие на скорость работы процессора и надежность передачи информации: * Первым из них является так называемая проблема представления отрицательных чисел. * Второй недостаток двоичной системы счисления получил название нулевой избыточности. Попытка преодолеть эти и другие недостатки двоичной системы счисления стимулировала использование в компьютерах других систем счисления и развитие собственно теории систем счисления. Выбирая систему кодирования информации в компьютере, разработчики в первую очередь думают о быстродействии процессора, т.е. о скорости обработки закодированной информации. Каждая операция в современных процессорах реализуется через так называемые предельные алгоритмы. В термин “предельный алгоритм” вкладывается следующий смысл: вся мощь современного математического аппарата и компьютерной инженерии была использована при его создании. Например, обычное сложение целых многоразрядных чисел реализуется “быстрым” рекурсивным алгоритмом с использованием операций сдвига. Стремясь увеличить вычислительную скорость компьютера, работающего на двоичной системе, разработчики ввели особое беззнаковое представление отрицательных целых чисел — так называемый дополнительный код. В десятичной системе счисления для представления отрицательных чисел человек использует знак числа. То, что привычно и хорошо для человека, выполняющего вычисления на бумаге, не всегда хорошо для компьютера. Для того чтобы сложить два целых числа с разными знаками, и человек, и компьютер, вообще говоря, должны выполнить следующие действия:
Многовато будет для простой и часто используемой операции! Для увеличения скорости работы процессора математики предложили все отрицательные целые числа записывать в дополнительном коде [1, 2], и тогда сложение двух целых чисел стало выполняться за одну операцию (т.е. без анализа знаков слагаемых). как влияет на скорость выполнения операций над целыми числами кодирование отрицательных целых чисел дополнительным кодом. Второй недостаток двоичной системы особенно неприятен при ее использовании для передачи информации. Нулевая избыточность двоичного представления означает, что в двоичной системе отсутствует механизм обнаружения ошибок, которые, к сожалению, неизбежно возникают в компьютерных системах. На заре развития двоичной компьютерной техники не возникал так остро вопрос о надежности передачи больших объемов информации, так как еще не существовали локальные компьютерные сети, не было Интернета, да, собственно, не произошло еще всеобщей информатизации. Но времена меняются… Суть этой проблемы состоит в следующем. Пусть в процессе передачи или хранения информации, представленной, например, двоичным кодом 11011010, под влиянием внешних или внутренних факторов произошло искажение информации, и она перешла в кодовую комбинацию 11010010 (искаженный разряд выделен). Поскольку комбинация 11010010 (как и любой другой двоичный код) является “разрешенной” в двоичной системе счисления, то без дополнительных действий невозможно определить, произошло искажение информации или нет. Для решения этой проблемы можно, например, для каждого байта (8 разрядов двоичного числа) считать количество единиц, или для группы байтов считать контрольную сумму и т.д. В любом случае должны быть использованы специальные методы избыточного кодирования, что замедляет работу компьютера и требует дополнительной памяти. В условиях, когда человечество все больше и больше зависит от надежности работы компьютерных систем (управление ракетами, самолетами, атомными реакторами, банковскими системами), вопрос об эффективных механизмах обнаружения ошибок выдвигается на передний план. Двоично-десятичная система В современных компьютерах и иных цифровых устройствах для ввода-вывода часто используется двоично-десятичная система счисления. Необходимость появления такой системы вызвана тем, что человек привык в своей деятельности использовать десятичную систему, а вычислительные устройства работают в двоичной. Каждая десятичная цифра записывается в виде наборов 0 или 1. Чтобы записать 10 различных обозначений для десятичных цифр требуется 4 бита. Соответственно, имеем следующие цифры: 0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001. Фактически, это запись соответствующих чисел в двоичной форме. Поэтому арифметические операции между цифрами сводятся к соответствующим операциям в двоичной системе счисления. Для корректирования результата операций с многозначными десятичными числами, приходится добавлять или вычитать значение 0110, соответствующее числу 6. Пример: число 365 в двоично-десятичной форме записывается как 0011 0110 0101. Составьте алгоритмы арифметических операций для двоично-десятичной системы счисления. Троичная система Использование классической двоичной системы счисления для представления информации в компьютере имеет существенные недостатки, влияющие на скорость работы процессора. Одним из них является так называемая проблема представления отрицательных чисел. Отрицательные числа в десятичной системе помечаются специальным знаком. Добавление еще одного знака к десяти имеющимся особой роли не играет. Добавление одного знака к имеющимся двум увеличивает число знаков в полтора раза! Поэтому принимались разные попытки записывать отрицательные числа, использоя только знаки 0 и 1. Прямой код – добавление в начало бита 0 для положительных и 1 – для отрицательных чисел. Обратный код – все цифры регистра, где хранится отрицательное число, меняются на противоположные (0 на 1, 1 на 0). Старший бит при этом показывает знак числа. Стремясь увеличить вычислительную скорость компьютера, работающего на двоичной системе, разработчики ввели особое беззнаковое представление отрицательных целых чисел — так называемый дополнительный код. Вычитание стало выполняться так же, как и сложение. А можно ли записывать целые отрицательные числа без знака, но и без дополнительного кода? Можно! Например, в любой P-ичной уравновешенной системе счисления все целые отрицательные числа записываются без знака [2, 6]. Троичную систему счисления можно построить, как и двоичную, взяв за основание число 3. Базой при этом будут числа 1, 3, 9, 27, 81, …, а цифрами (алфавитом) 0, 1 и 2. Троичная уравновешенная система имеет алфавит - символы { 1, 0, 1}, где 1 равно -1. Глядя на таблицу, понятно, почему эту систему назвали уравновешенной, или симметричной. Очевидно, знак для представления отрицательных чисел не нужен!
сформировать правила построения таблиц сложения и умножения и правила арифметических операций для целых чисел. В 60-х годах XX столетия в МГУ им. М.В. Ломоносова была создана троичная ЭВМ “Сетунь”, запущенная потом в серию. Для кодирования информации в этой машине использовалась троичная уравновешенная система счисления, вместо бита использовался трит, вместо привычной двоичной логики — троичная. Разработчик этой ЭВМ Николай Петрович Брусенцов. Понятие избыточности информационной системы Известно, что каналы, по которым передается информация, практически никогда не бывают идеальными (каналами без помех). Помехи в каналах образуются по разным причинам, но результат их воздействия на передаваемую информацию всегда один — информация теряется (искажается). В теории связи известно, что избыточность кода позволяет обеспечивать надежную защиту системы и ее помехоустойчивость. Под потерей информации мы будем понимать искажение информации при сохранении переданного объема данных. Например, по каналам связи был передан код доступа к серверу в виде двоичного кода 10101100 10100000 11100000 11100001 (слово “марс” в кодировке ASCII). Длина переданного кода (т.е. объем информации) равна четырем байтам, или 32 битам. Сервер получил этот код в виде: 10101100 10100100 11100000 11100001. Проанализируем ситуацию: 1) формально передача завершена успешно, так как полученный код является допустимой комбинацией в двоичной системе счисления; 2) длина принятого кода равна длине отправленного кода (при успешной передаче нельзя физически потерять один или несколько битов, можно только изменить содержимое битов); 3) произошло изменение (искажение) содержимого одного бита: с точки зрения пользователя, информация при передаче пропала (слово “мдрс” не равно слову “марс”). В результате пользователю в доступе к серверу отказано! При передаче информации всегда важно знать ответы на два вопроса: 1) произошло ли искажение (потеря) информации? 2) если произошло искажение, то в каких битах (разрядах)? Для ответа на эти вопросы необходимо, чтобы передаваемые коды обладали свойством избыточности. Или, что то же самое, символьная система, при помощи которой кодируется информация, должна обладать свойством избыточности. В информатике под избыточностью понимают следующее: код обладает свойством избыточности, если количество бит в нем больше, чем это необходимо для однозначного декодирования (восстановления) исходной информации. Информация кодируется не только в компьютерах. Мы можем считать, что наша письменная речь — это информация, закодированная русскими буквами. Представьте, что вам в руки попадет записка с частично стертыми буквами: Вы**т со*т**т** в н*ч*ле н**бр*. Подумав, вы сможете восстановить текст этой записки, причем однозначно. А ведь из 27 букв записки 12 букв были уничтожены! Отметим, что для однозначного восстановления потерянной информации важно знать, на каких местах стояли стертые буквы. Вы смогли восстановить текст записки потому, что русский язык обладает избыточностью. В русском языке существуют слова, однозначно прочитываемые в случае “потери” некоторых букв. Например, С_НТ_БР_, КИ_ТЬ, Д_Р_В_. Имея текст на русском языке с частично “потерянными” буквами, человек, хорошо владеющий русским языком, сможет однозначно восстановить его. Например, вы без труда прочитаете предложение с пропущенными буквами “П_тр И___ч Ч_йк__ск_й - в_д __щ_й__ р_с__ий к_мп__ит_р”. Однако если это предложение будет читать иностранец, едва знающий русский язык и русскую историю, то он не сможет понять, что написано в данном предложении. Мы, носители русского языка, можем с легкостью восстановить окончания, пропущенные буквы в слогах, и можем подобрать подходящие слова (из тех, что нам известны). А иностранцу просто не с чем сравнивать получаемую информацию! Таким образом, для носителя языка обычный связный текст на его родном языке содержит избыточную информацию — ее можно удалить, но смысл текста (для носителя языка) сохранится. Избыточностью обладает не только русский, но и любой другой язык. Выдающийся американский инженер и математик, основатель теории информации Клод Шеннон проделал такой эксперимент. В литературном английском тексте были удалены 50% букв. Пробелы между словами оставались неизменными, буквы удалялись, конечно, не случайным образом. Например, в английских словах за буквой qвсегда следует только буква u, поэтому “потерянная” буква u может быть всегда восстановлена. После “искажения” текст давали читать носителям языка, обладающим достаточно высоким культурным уровнем. Поразительно, но практически все участники этого эксперимента смогли восстановить искаженный текст полностью! Итак, для обнаружения и восстановления потерянной информации необходимо, чтобы символьная система, при помощи которой кодируется информация, обладала избыточностью. К сожалению, двоичная система счисления не обладает избыточностью, поэтому и говорят, что она обладает нулевой избыточностью. С целью предотвращения потери информации при передаче данных, кодированных в двоичной системе счисления, были придуманы избыточные коды (коды с избыточностью). Существуют избыточные коды с обнаружением (они только обнаруживают ошибку) и коды с исправлением (эти коды обнаруживают место ошибки и исправляют ее). В разных каналах передачи информации возникают разные помехи. Поэтому инженеры и ученые вынуждены разрабатывать различные по своей структуре и избыточности коды. Так, при записи информации на лазерные диски применяют коды с избыточностью по длине в 25%. Примерно с такой же избыточностью применяют коды в системах цифрового спутникового ТВ. Понятно, что использование избыточных кодов приводит к снижению скорости работы компьютеров, увеличению объема передаваемых сообщений и, соответственно, снижению скорости передачи информации. Известно, и мы это покажем, что фибоначчиева система счисления обладает избыточностью. |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||