Понятие о позиционных системах счисления

0 -2 1 (75)₁₀ = (1001011)₂

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

1.2.2. Перевод чисел в двоичной, восьмеричной и шестнадцатеричной системах счисления

Для перевода восьмеричного числа в двоичную систему счисления достаточно заменить каждую цифру восьмеричного числа её представлением в двоичной системе счисления (трехразрядным двоичным числом). Например:

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

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

Это же число в шестнадцатеричной системе счисления имеет вид:

1.3. Двоичная арифметика

Правила выполнения арифметических действий в двоичной системе счисления определяются таблицами сложения, вычитания и умножения:

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

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

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

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

1.4. Двоично-десятичный код

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

Способов кодирования существует несколько. Одним из широко применяемых является код 8421, в котором каждая цифра десятичного числа заменяется соответствующим четырехразрядным двоичным числом так же, как и для шестнадцатеричных чисел, но комбинации большие 9 не используются. Например, число (19 205 463)₁₀ в двоично-десятичном коде имеет вид:

.

1.4.1. Арифметические действия над двоично-десятичными кодами

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

При выполнении операции сложения одного разряда двух десятичных чисел перенос возникает, если их сумма больше девяти, а в двоичной тетраде (четырех разрядах двоичного числа) перенос будет, если число больше 15. Поэтому если при сложении одного разряда двух двоично-десятичных кодов на двоичном сумматоре сумма получилась больше 9 или есть перенос, то к этому разряду прибавляют ещё число 6 (дополнение до полной кодовой комбинации 15). При этом выполняется перенос в старшую тетраду, а в тетраде складываемого разряда получается число, соответствующее десятичному сложению. И так поступают с каждым разрядом двоично-десятичного кода.

Например, надо сложить два числа (79)₁₀ = (0111 1001) и (38)₁₀ = (0011 1000) в двоично-десятичном коде.

Складываем младший разряд: 1001 + 1000 = 0001 + перенос в следующий десятичный разряд. Проводим десятичную коррекцию (прибавляем число (6) = 0110) и получаем младший разряд суммы 0001 + 0110 = 0111.

Складываем числа следующего десятичного разряда и с учетом переноса получаем: 0111 +0011 + 1(перенос) = 1011. Эта двоичная комбинация соответствует числу, большему 9. Поэтому проводим десятичную коррекцию в этом разряде: 1011 + 0110 = 0001 + (перенос в следующий разряд). В третьем разряде слагаемые имеют цифру 0, с учетом переноса получим двоичный код 0001. Таким образом, двоично-десятичный код суммы имеет вид:

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

1.5. Вопросы для повторения

1. Что называется системой счисления?

2. Что такое позиционная система счисления?

3. Что такое основание системы счисления?

4. Что такое разряд числа?

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

6. Каковы достоинства двоичной системы счисления?

7. Когда применяется шестнадцатеричная и восьмеричная системы счисления?

8. Когда используется двоично-десятичный код?

2. ДВОИЧНЫЕ КОДЫ ПЕРЕДАЧИ ИНФОРМАЦИИ
И ЗАЩИТА ИХ ОТ ПОМЕХ

2.1. Стандартные коды обмена информацией

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

Рассмотрим двоичный семиразрядный стандартный код обмена информацией КОИ-7, который приведён в табл. 1. Из семи разрядов старшие три разряда определяются номером столбца, а младшие четыре разряда - номером строки таблицы, на пересечении которых находится кодируемый символ. Сочетаниями букв задаются значения служебных кодовых комбинаций, например: 3В (звонок) - выдача звукового сигнала, ПС (перевод строки) - переход на следующую строку, ВК - возврат курсора или каретки печатающего устройства и т.д.

Таблица 1

D6

D5

D4

D3

D2

D1

D0

A B C D E F

ЗВ ГТ ПС ВК ЛАТ РУС

- ! “ % & , ( ) * + - /

: ; < = > ?

@ A B C D E F G H I J K L M N O

P Q R S T U V W X Y Z [ \ ] ^

Ю А Б Ц Д Е Ф Г Х И Й К Л М Н О

П Я Р С Т У Ж В Ь М З Ш Э Щ Ч ЗБ

Рассмотрим, какие коды (в шестнадцатеричной системе) необходимо подать, чтобы на экране дисплея получилось сообщение:

КОД

КОИ-7 .

Для получения такой картины сообщения на экране дисплея необходимо выполнить следующие действия: перейти на новую строку, вывести два пробела, вывести последовательно буквы К, О и Д, перейти на следующую строку, вывести один пробел, вывести последовательно буквы К, О и И, символ -, цифру 7, а затем выдать звуковой сигнал о завершении вывода информации. Этим действиям (см. табл. I) соответствуют коды: 0АН, 20Н, 20Н, 6ВН, 6FH, 64Н, 0AН, 20Н, 6ВН, 6FН, 69Н, 2DН, 37Н, 07Н - всего 14 шестнадцатеричных кодов. Если эти коды последовательно вывести на дисплей, то получим требуемое сообщение.

2.2. Однопеременные коды

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

Одним из важных классов комбинаторных кодов являются однопеременные коды, у которых две смежные кодовые комбинации отличаются только одним изменением в каком-либо разряде (говорят, кодовое расстояние между комбинациями равно 1). Например, два смежных числа (7)₁₀ = (0111)₂ и (8)₁₀ = (1000)₂ в нормальном двоичном коде отличаются изменениями во всех разрядах, в однопеременных кодах допустимы последовательные комбинации ... 0010, 0011, 0111, 0101 и т.д.

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

Рис. 1. Схема кодового датчика

Рис. 2. Диаграмма Карнауга

При повороте шкалы с простым двоичным кодом из позиции 3 в позицию 4 и обратно одновременно все три элемента съёма информации располагаются на границе перехода из 0 в 1. Обеспечить одновременное переключение всех трех элементов практически невозможно, а срабатывание какого-либо элемента раньше выдаст ложную информацию, соответствующую другой позиции шкалы, что приведёт к появлению ошибки в работе всей системы управления.

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

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

Чтобы получить однопеременный код, достаточно наметить определенный путь обхода точек диаграммы и последовательно выписать номера этих точек. Для пути, показанного на рис.2, последовательность кодовых комбинаций имеет вид: 0 - 0000, 1 - 0001, 2 - 0011, 3 - 0010, 4 - 0110, 5 - 0111, 6 - 0101, 7 - 0100, 8 - 1100, 9 - 1101, 10 - 1111, 11 - 1110, 12 - 1010, 13 - 1011, 14 - 1001, 15 - 1000 .

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

2.3. Помехоустойчивое кодирование

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

Если длина кода n - разрядов, то таким двоичным кодом можно представить максимум 2ⁿ различных слов. Если все разряды слова служат для представления информации, то код называется простым (неизбыточным). Например, таким кодом является код КОИ-7. Коды, в которых лишь часть кодовых разрядов используется для представления информации, называются избыточными. Часть слов в избыточных кодах являются запрещёнными, и их появление при передаче информации свидетельствует о наличии ошибки. Принадлежность слова к разрешённым или запрещённым словам определяется правилами кодирования, и для различных кодов эти правила различны.

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

Простой (неизбыточный) код имеет минимальное расстояние d = 1. Если d >= 2, то любые два слова в данном коде отличаются не менее чем в двух разрядах, следовательно, любая одиночная ошибка приведет к появлению запрещенного слова и может быть обнаружена.

Если d >= 3, то любая одиночная ошибка создает запрещённое слово, отличающееся от правильного в одном разряде, а от любого другого разрешенного слова - в двух разрядах. Заменяя запрещённое слово ближайшим к нему (по кодовому расстоянию) разрешенным словом, можно исправить одиночную ошибку.

Рассмотрим некоторые типичные коды.

2.3.1. Код с проверкой на чётность

Код с проверкой четности образуется добавлением к группе информационных разрядов, представлявших простой (неизбыточный) код, одного избыточного (контрольного) разряда. При формировании кода слова в контрольный разряд записывается 0 или 1 таким образом, чтобы сумма единиц в слове, включая избыточный разряд, была четной в случае контроля на четность (или нечетной в случае контроля на нечетность). Если при передаче информации приемное устройство обнаруживает, что в принятом слове сумма единиц не соответствует четности, то это воспринимается как признак ошибки. Например, при передаче латинской буквы F (см. табл. 1, код 1000110 ) к её двоичному коду будет добавлен контрольный разряд, равный 1, чтобы число всех единиц было четным, и будет передано 11000110, где самый старший, восьмой разряд - контрольный.

Минимальное расстояние кода d = 2, поэтому код с проверкой четности обнаруживает все одиночные ошибки (а также любое нечетное количество ошибок), однако, две ошибки (и любое четное количество ошибок) этот код не обнаруживает.

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

2.3.2. Код Хемминга

Этот код был предложен Р.В. Хеммингом в 1950 году. Он позволяет обнаруживать и исправлять одну ошибку (кодовое расстояние d = 3).

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

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

Далее полагают, что младший контрольный разряд контролирует четность разрядов, двоичный номер которых имеет единицу в младшем разряде, т.е. 1, 3, 5, 7, 9, 11 разряды (в двоичном коде: 0001, 0011, 0101, 0111, 1001, 1011). Следующий контрольный разряд проверяет разряды, двоичные номера которых имеют единицу во втором разряде, т.е. 2, 3, 6, 7, 10, 11 (в двоичном коде: 0010, 0011, 0110, 0111, 1010, 1011). Третий контрольный разряд контролирует разряды с двоичными номерами, имеющими единицу в третьем разряде, т.е. 4, 5, 6, 7, 12 (двоичные коды: 0100, 0101, 0110, 0111, 1100). Четвертый, старший контрольный разряд контролирует разряды номер 8, 9,10, 11, 12 (в двоичном коде: 1000, 1001, 1010, 1011, 1100).

Для упрощения кодирования в качестве контрольных разрядов берем те, которые встречаются только в одной из перечисленных групп номеров разрядов, т.е. разряды 1, 2, 4, 8. Тогда размещение разрядов в передаваемом коде будет следующим (контрольные разряды подчеркнуты):

При этом разряды D12 D11 D10 D9 D7 D6 D5 D3 образуют байт передаваемой информации, а разряды D8 D4 D2 D1 - избыточные, обеспечивают определение и исправление ошибок. Составим таблицу формирования контрольных разрядов (табл. 2).

Таблица 2

Контрольные разряды формируются следующим образом: им дается значение 0 или 1 так, чтобы сумма проверяемых разрядов согласно табл. 2 была четной.

Например: необходимо передать букву Z. Ее двоичный код имеет вид: 1011010 (см. табл. 1). Передаваемый код Хемминга в информационных разрядах имеет значения: 0101 D8 101 D4 0 D2 D1 и согласно табл. 2 для обеспечения четности суммы проверяемых разрядов контрольные разряды должны иметь значения: D1 = 0, D2 = 0, D4 = 0, D8 = 0. Таким образом, полностью передаваемый код будет иметь вид: 010101010000.

2.3.2.1. Проверка кода Хемминга

После приема передаваемого кода проводится его проверка на наличие ошибки. Для этого определяется корректирующее число путем анализа четности суммы проверяемых разрядов (см. табл. 2). Первая группа дает младший разряд числа, вторая - второй разряд, третья группа - третий, четвертая - старший, четвертый разряд корректирующего числа. Если сумма четная, то соответствующий разряд корректирующего числа равен 0, если нечетная, то разряд равен 1.

Корректирующее число указывает номер разряда, в котором произошел сбой информации, и информацию в этом разряде надо инвертировать. Если корректирующее число равно нулю, то ошибки при передаче не произошло. Предположим, что в рассматриваемом нами коде при приеме возникла ошибка в пятом разряде: 0101010(0)0000.

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

D1+D3+D5+D7+D9+D11 = 0+0+0+1+1+1 = 3,

D2+D3+D6+D7+D10+D11= 0+0+0+1+0+1 = 2,

D4+D5+D6+D7+D12= 0+0+0+1+0 = 1,