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

Содержание 

Введение…………………………………………………………………….……3

Глава 1. Использование систем счисления в информатике

1.1. Понятие системы счисления…………………………………….…….……4

1.2. Непозиционные и позиционные системы счисления…………..…………9

1.3. Двоичное кодирование информации в компьютере……….…..…….…..14

1.4. Представление чисел в компьютере………………….………………..….16

1.5. Способы построения двоичных кодов………….…………………………18

Глава 2. Алгоритм решения задачи….……………………………………...….26

Заключение…………………………………………………………………...….31

Список  использованной литературы…………………………….…….……....32 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Введение

     Столь привычная для нас десятичная система оказалась неудобной  для электронно-вычислительных машин (ЭВМ). Если в механических вычислительных устройствах, использующих десятичную систему, достаточно просто применить элемент с множеством состояний (колесо с девятью зубьями), то в электронных машинах надо было бы иметь 10 различных потенциалов в цепях. Наиболее просто реализуется элементы с двумя состояниями - триггеры. Поэтому естественным был переход на двоичную систему, т.е. системы по основанию 2. В этой системе всего две цифры - 0 и 1 . Каждая цифра называется двоичной (от английского binary digit - двоичная цифра). Сокращение от этого выражения привело к появлению термина бит, ставшего названием разряда двоичного числа.

     Бит - это минимальная единица измерения  информации (0 mini). За битом следует байт, состоящий из восьми бит, затем килобайт (кбайт) - 1024 байта, мегабайт (мбайт) - 1024 кбайта, гигобайт (гбайт) - 1024мбайт.

         Цель курсовой работы – рассмотреть системы счисления с компьютерной обработке. 
 
 
 
 
 
 
 
 
 
 
 
 

     Глава 1. Использование систем счисления в информатике

     1.1 Понятие системы счисления

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

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

     Запись  произвольного числа x в P-ичной позиционной системе счисления основывается на представлении этого числа в виде многочлена

     x = a_nPⁿ + a_n-1P^n-1 + ... + a₁P¹ + a₀P⁰ + a_-1P^-1 + ... + a_-mP^-m

     Арифметические  действия над числами в любой  позиционной системе счисления  производятся по тем же правилам, что  и десятичной системе, так как  все они основываются на правилах выполнения действий над соответствующими многочленами. При этом нужно только пользоваться теми таблицами сложения и умножения, которые соответствуют данному основанию P системы счисления. В электронных вычислительных машинах применяют позиционные системы счисления с недесятичным основанием: двоичную, восьмеричную, шестнадцатеричную и некоторые другие. Наибольшее распространение в вычислительных машинах имеет двоичная система счисления. В этой системе используются только две цифры: 0 (нуль) и 1 (единица). Двоичное изображение числа требует большего (для многоразрядного числа примерно в 3,3 раза) количества разрядов, чем его десятичное представление.

     Тем не менее, применение двоичной системы позволяет уменьшить общее количество аппаратуры и создаёт большие удобства для проектирования цифровых вычислительных машин, так как для представления в машине разряда двоичного числа может быть использован любой простой элемент, имеющий всего два устойчивых состояния. Такими элементами, например, являются реле, триггерные схемы и т.п. Для представления десятичного разряда потребовалось бы четыре таких элемента. Помимо двоичной системы счисления в вычислительной технике используется также другие системы с недесятичным основанием - восьмеричная и шестнадцатеричная, имеющие основанием соответственно числа 8 и 16. В восьмеричной системе употребляются восемь цифр: 0, 1, 2, 3, 4, 5, 6, 7. В шестнадцатеричной системе для изображения чисел употребляется 16 чисел от 0 до 15. При этом, чтобы одну цифру не изображать двумя знаками, приходится вводить специальные обозначения для цифр, больших девяти. Первые десять цифр этой системы обозначают цифрами от 0 до 9, а старшие пять цифр - латинскими буквами: A, B, C, D, E, F.

     В основе современной электронной  вычислительной техники лежат числа и системы счисления, которые эти числа порождают. От эффективности последних зависят параметры вычислительных систем и устройств, в первую очередь показатели быстродействия и надежности². Среди систем счисления наибольшее распространение в вычислительной технике нашла двоичная система счисления. Эта система в силу своей простоты, выражающейся в нулевой сложности ее структуры, обеспечивает необходимый уровень основных параметров этой техники и пока что находится вне конкуренции. Однако сегодня обстановка в вычислительной технике вследствие значительных технологических достижений в области производства интегральных схем начинает радикально меняться, так как эти технологии позволяют в одной микросхеме размещать миллионы логических элементов, снизив тем самым в разы стоимость интегральных микросхем и повысив, при этом, их быстродействие. Отказоустойчивость этих микросхем, по крайней мере, на сегодня, даже возросла, что нельзя сказать об их устойчивости к помехам, вызываемых сбоями в работе. Сбои – это достаточно распространенное явление в вычислительной технике и новые технологии не решают кардинально вопрос помехоустойчивости, а наоборот, иногда, в силу большой плотности логических элементов на одной подложке интегральной схемы и снижения напряжения питания для увеличения ее быстродействия, даже усугубляют его. Чтобы убедиться, что это действительно так, достаточно хотя бы вспомнить нередкие зависания компьютеров. Но компьютеры - это лишь видимая вершина айсберга в многочисленных применениях вычислительной техники и цифровых устройств³. Их зависания, хотя и неприятны, но можно пережить. Значительно хуже дело обстоит с вычислительными системами и устройствами, где ошибки не допустимы, и тем более с техникой, работающей в реальном масштабе времени, где не остается времени на повторную операцию вычисления или передачу информации. Там ошибку необходимо не только обнаружить, а еще в тот же момент, когда она обнаружена, и исправить, то есть в данном случае речь идет о технике способной не только обнаруживать помехи, а и их исправлять. Двоичная же система счисления, в силу своей предельной простоты, не обладает внутренней (естественной) избыточностью информации в своей структуре и, как следствие, не способна решать других задач, кроме задач арифметико-логических. Тем более она не может без посторонней помощи, которая проявляется во введении в нее внешней искусственной избыточной информации, обнаруживать и исправлять ошибки в своей работе. А такая внешняя избыточность, которая на сегодня широко используется в вычислительной технике, приводит к значительному росту аппаратурных затрат и соответственно к снижению надежности и быстродействия использующих ее вычислительных устройств. Поэтому этот хорошо отработанный путь повышения помехоустойчивости и отказоустойчивости вычислительной техники в какой-то степени в перспективе является тупиковым. Однако существуют системы счисления и с более сложной структурой, чем двоичная система, – интеллектуальные (структурные), которые в силу не равной нулю сложности их структур способны за счет внутренне присущей им естественной избыточности информации обнаруживать и исправлять ошибки в своей работе. То есть такие системы счисления изначально, по своей природе, обладают свойствами помехоустойчивости и самоконтроля. Кроме обычных арифметико-логических функций и защиты от помех такие системы счисления способны решать и другие более сложные задачи как, например, сжатия и защиты информации от несанкционированного доступа, порождения и перебора комбинаторных объектов, решения задач комбинаторной оптимизации и другие⁴. Важно также и то, что эти системы счисления указанные задачи решают в аппаратном исполнении, что уже само по себе повышает надежность и быстродействие их работы, причем в разы. Но, кроме этого, быстродействие в них растет и за счет использования более простых алгоритмов работы по сравнению с алгоритмами, использующими двоичные системы счисления.

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

     1.2 Непозиционные и позиционные системы счисления

     Совокупность  приемов наименования и записи чисел  называется счислением. Под системой счисления понимается способ представления любого числа с помощью ограниченного алфавита символов, называемых цифрами. Счисление представляет собой частный случай кодирования, где слово, записанное с использованием определенного алфавита и по определенным правилам, называется кодом. Применительно к счислению это код числа. Различают позиционные и непозиционные системы счисления. В непозиционных системах счисления каждое число обозначается соответствующей совокупностью символов. Характерным представителем непозиционных систем является римская система счисления со сложным способом записи чисел и громоздкими правилами выполнения арифметических операций. Например, запись MCMXCIX означает, что записано число 1999 (М - тысяча, С - сто, Х - десять, V - пять, I - единица и т.д.).

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

     В позиционной системе счисления  значение числа определяется не только набором входящих в него цифр, но и их местом (позицией) в последовательности цифр, изображающих это число, например, числа 127 и 721⁶.

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

     Количество  символов, используемых в позиционной  системе счисления, называется ее основанием. Его обозначают обычно буквой q. В  десятичной системе счисления используется десять символов (цифр): 0, 1, 2, 3,4, 5, 6, 7, 8, 9, и основанием системы является число десять.

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

     В общем случае в такой позиционной  системе счисления с основанием q любое число Х может быть представлено в виде полинома разложения:

     диск  (1.1)

     где: A(q) - запись числа в системе счисления  с основанием q; q - основание системы счисления; ai - целые числа, меньше q; п - число разрядов (позиций) в целой части числа; т - число разрядов в дробной части числа.

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

     A(q)=a_n-1 a_n-2…a₁a₀,a_-1…a_-m (1.2)

     Запятая отделяет целую часть числа от дробной и служит началом отсчета  значений веса каждой позиции (разряда).

     В информатике применяют позиционные системы счисления с недесятичным основанием: двоичную, восьмеричную и шестнадцатеричную, т.е. системы счисления с основанием q = 2^k , где k=1,3,4. Наибольшее распространение получила двоичная система счисления⁷. В этой системе для представления любого числа используются два символа - цифры 0 и 1. Основание системы счисления q = 2. Произвольное число с помощью формулы (1.1) можно представить в виде разложения по степеням двойки. Тогда условная сокращенная запись в соответствии с (1.2) означает изображение числа в двоичной системе счисления (двоичный код числа), где ai =0 или 1.

     Двоичное  представление числа требует  примерно в 3,3 раза большего числа разрядов, чем его десятичное представление. Тем не менее, применение двоичной системы счисления создает большие удобства для работы ЭВМ, т. к. для представления в машинеразряда двоичного числа может быть использован любой запоминающий элемент, имеющий два устойчивых состояния. В восьмеричной системе счисления алфавит состоит из восьми символов (цифр): 0, 1 ... 7. Основание системы счисления q = 8. Для записи произвольного числа в восьмеричной системе счисления необходимо по формуле (1.1) найти его разложение по степеням восьмерки, а затем воспользоваться условной сокращенной записью (1.2).

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

     Преобразование  числа Х из системы счисления  с основанием q в систему счисления с основанием р осуществляется по правилу замещения или по правилу деления-умножения на основание системы счисления.

     Правило замещения реализуется на основании  формулы (1.1) и предусматривает выполнение арифметических операций с кодами чисел в новой системе счисления. Поэтому оно чаще всего используется для преобразования чисел из недесятичной системы счисления в десятичную. Пример.111011,011₍₂₎= 1•2⁴ +0•2³ +1•2² +0•2¹ +l•2⁰+0•2^-1+l•2^-2+l•2^-3= 59, 375.

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

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

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

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

     Таким образом, в результате преобразования получаем 75,35₍₁₀₎ = 1001011,01011...₍₂₎. Как следует из примера, процесс перевода дробной части можно продолжить до бесконечности. ЭВМ оперирует числами, представленными конечными наборами цифр. Поэтому дроби округляют в соответствии с правилами преобразования и весом младшего разряда исходной дроби.

     Преобразование  чисел из двоичной системы счисления  в восьмеричную, шестнадцатеричную  и обратно осуществляется по упрощенным правилам с учетом того, что основания  этих систем счисления кратны целой степени 2, т. е. 8=2³ , а 16=2⁴ . Это означает, что при преобразовании восьмеричного кода числа в двоичный, необходимо каждую восьмеричную цифру заменить соответствующим трехзначным двоичным кодом (триадой). При преобразовании шестнадцатеричного кода числа в двоичный необходимо каждую шестнадцатеричную цифру заменить четырехзначным двоичным кодом (тетрадой). При преобразовании двоичного кода в восьмеричный или шестнадцатеричный двоичный код делится соответственно на триады или тетрады влево и вправо от запятой (точки), разделяющей целую и дробные части числа. Затем триады (тетрады) заменяются восьмеричными (шестнадцатеричными) цифрами. При представлении числа Х в форме с фиксированной точкой указываются знак числа (sign X) и модуль числа (modX) в q-ичном коде. Иногда такую форму представления чисел называют естественной формой. Место точки (запятой) постоянно для всех чисел и в процессе решения задач не меняется. Знак положительного числа кодируется цифрой «0», а знак отрицательного числа - цифрой «1».

     Код числа в форме с фиксированной  точкой, состоящий из кода знака  и q-ичного кода его модуля, называется прямым кодом. Разряд прямого кода числа, в котором располагается код  знака, называется знаковым разрядом кода. Разряды прямого кода числа, в которых располагается q-ичный код модуля числа, называются цифровыми разрядами кода. При записи прямого кода знаковый разряд располагается левее старшего цифрового разряда и обычно отделяется от цифровых разрядов точкой⁹. 

     1.3. Двоичное кодирование информации в компьютере

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

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

     Создатели первых компьютеров столкнулись  с проблемой представления и  обработки информации. Так как  компьютер это всего лишь машина у которой нет ни интеллекта, ни логики, и мыслить она не способна, разработчикам пришлось найти такой способ представления информации, который был бы максимально прост для восприятия компьютером. Столь привычная для нас десятичная система оказалась неудобной для ЭВМ. Если в механических вычислительных устройствах, использующих десятичную систему, достаточно просто применить элемент с множеством состояний (колесо с девятью зубьями), то в электронных машинах надо было бы иметь 10 различных потенциалов в цепях. Наиболее просто реализуется элементы с двумя состояниями - триггеры. Поэтому естественным был переход на двоичную систему, т.е. системы по основанию 2. В этой системе всего две цифры - 0 и 1 . Каждая цифра называется двоичной (от английского binary digit - двоичная цифра). Сокращение от этого выражения привело к появлению термина бит, ставшего названием разряда двоичного числа.

     Бит - это минимальная единица измерения  информации (0 или1). За битом следует  байт, состоящий из восьми бит, затем  килобайт (кбайт) - 1024 байта, мегабайт (мбайт) - 1024 кбайта, гигобайт (гбайт) - 1024мбайт¹¹.

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

     Таким образом, информация представляется в  виде конечной последовательности 0 и 1. Например целое неотрицательное число А₂=Т 11110000₂ будет храниться в ячейке следующим образом:

     Значит, мы можем записать все числа от 0 до 255 в двоичной системе счисления  в 1 ячейке памяти.

     1.4. Представление чисел в компьютере

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

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

     Например, число 19₁₀ будет выглядеть:

     Для хранения целых чисел со знаком (отрицательных) отводиться две ячейки памяти (16 битов), причем старший (левый) разряд отводиться под знак числа (если число положительное, то в знаковый разряд записывается 0, если отрицательное - 1).

     Например, число -98₁₀ будет выглядеть:

     Представление целых чисел в компьютере в  формате «знак - величина» называется прямым кодом числа. Например, число 200210=11111010010₂ будет представлено в шестнадцатиразрядном представлении следует следующим образом:

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

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

     2ⁿ-|А|+|А| =0

     поскольку в компьютерной 2ⁿ=0.

     Алгоритм  построения такого кода довольно прост:

     1. Записать модуль числа в прямом коде.

     2. Получить обратный код числа  (то есть заменить все нули  на единицы, а все единицы  на нули).

     3. К полученному результату прибавить  единицу.

     Запишем дополнительный код отрицательного числа -2002 для 16-разрядного представления:

     Запишем дополнительный код отрицательного числа -16320 для 16-разрядного представления:

     1.5. Способы построения двоичных кодов

     Начиная с конца 60-х годов, компьютеры все  больше использовать для обработки  текстовой информации и в настоящее  время большая часть компьютеров в мире занято именно обработкой текстовой информации¹².

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

     Но  способов построения таких кодов  очень много, рассмотрим некоторые  из них¹³:

     Алфавитное  неравномерное двоичное кодирование

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

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

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

      Рассмотрим  пример построения двоичного кода для  символов русского алфавита: 
 
 
 
 
 
 
 
 
 
 
 
 

     Неравномерный код с разделителями

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

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

     — код признака конца знака может быть включен в код буквы, поскольку не существует отдельно (т.е. кода всех букв будут заканчиваться 00);

     — коды букв не должны содержать двух и более нулей подряд в

     середине (иначе они будут восприниматься как конец знака);

     — код буквы (кроме пробела) всегда должен начинаться с 1;