Перевод чисел из Д-кода в двоичный и из двоичного в Д-код

Пусть задано 4-х разрядное число в коде Д1 A = a4a3a2a1, каждая десятичная цифра которого должна быть представлена в виде

ai = {4 3 2 1 }i . В данном случае i = 1, 2, 3, 4. Как нам уже известно, изображение числа А можно представить в следующем виде:

A = a4103+ a3102+ a2101+ a1100,

Как видно из этой формулы, при переводе из кода Д1в двоичный код каждый i-тый разряд кода Д1 надо умножать на 10I-1, т.е.

a11 , a210 , a3100 , a41000 .

В то же время 10 = 8 + 2 = 23+ 21 , значит

a1= {4 3 2 1 }1

a2 = {4 3 2 1 }2 (23+ 21)

a3= {4 3 2 1 }3 (23+ 21) (23 + 21)

a4= {4 3 2 1 }4 (23+ 21) (23 + 21) (23 + 21)

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

Например, переведем 2510= 0010 0101 в двоичную систему счисления. Вторую тетраду (0010) сдвигаем на 3 разряда влево, получаем 0001 0000. Эту же тетраду сдвигаем на 1 разряд влево и складываем с полученной:

0001 0000

+0000 0100

0001 0100

+0000 0101 (первая тетрада)

0001 1001 = 2510

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

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

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

Например, 1100012 = 4910 переведем в код Д1.

1) Сдвиг 1 10001

2) Сдвиг 1 1 0001

3) Сдвиг 1 1 0 001

4) Сдвиг и коррекция +0110 1 0 1 1 0 1 0 0 01

Рез.-т после корр. 1 0 0 1 0 01

5) Сдвиг 1 0 0 1 0 0 1

6) Сдвиг 1 0 0 1 0 0 1

Ответ 0100 1001D = 4910.

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

Глава 6

Информационные основы цифровых автоматов

6.1. Понятие об информации и её преобразованиях

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

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

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

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

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

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

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

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

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

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

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

6.2. Преобразования алфавитной информации

В наиболее общем виде преобразование алфавитной информации может быть следующим способом. Пусть даны два конечных алфавита и . Обозначим через совокупность всех слов конечной длины в алфавите Х, через - совокупность всех слов конечной длины в алфавите Y. Если исходная информация записывается в алфавите Х, а конечная информация – в алфавите Y, то произвольное преобразование информации будет представлять собой не что иное, как отображение множества F в множестве G.

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

Целесообразно в общем случае считать частичным отображением, т.е. задавать отображение не обязательно на всем множестве F, а лишь на части этого множества. Введение частичных отображений позволяет вместо отображений одного множества слов в другое рассматривать лишь отображение таких множеств в себя. Для этой цели достаточно ввести объединенный алфавит и множество слов в этом алфавите. Ясно, что вместо отображения (или частичного отображения) множества F в множество G можно рассматривать частичное отображение множества Н в себя. Это частичное отображение будет определено для слов, состоящих только из букв .

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

Пример 1 (зеркало) – эквивалентное. Пример 2 (сумма двух чисел) – не эквивалентное.

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

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

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

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

, .

Понятие об алгоритме

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

Каковы способы задания алфавитных операторов?

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

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

Недостаток определения алгоритма – отсутствие математической точности.

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

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

Пример: существует алфавит ; таблица подстановок:

1. ;

2. ;

3. .

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

1) ;

2) ;

3) ;

4) далее не применима ни одна формула.

Результат: .

Установлено, что любой алгоритм эквивалентен некоторому нормальному алгоритму.