Перевод правильной дроби из кода Д1 в двоичную систему счисления

Билет

1. Математической моделью систем с памятью является абстрактный автомат, определяемый как кортеж S=(A,Z,W,d,l, a₀), у которого

· A={a₀,a₁, …, a_m, …, a_M} - множество состояний (алфавит состояний), содержащее не менее двух элементов;

· Z={z₁,z₂, …, z_F} - множество входных сигналов (входной алфавит);

· W={w₁,w₂, …, w_G} - множество выходных сигналов (выходной алфавит);

· d : A´Z ®A - функция переходов, реализующая отображение пары "состояние - входной сигнал" в некоторое состояние автомата, т.е. d(a_m,z_f) = a_s, a_m,a_s Î A;

· l : A´Z ® W - функция выходов для автомата Мили, она ставит в соответствие паре "состояние автомата - входной сигнал" некоторый выходной сигнал, т.е. l(a_m,z_f) = w_g;

· l : A®W функция выходов для автомата Мура, т.е. l(a_m)=w_f, w_f Î W;

· а₀ - начальное состояние автомата.

Рисунок 2 Абстрактный автомат

Абстрактный автомат, рис. 1, имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t=0,1,2,… В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата А, причем в начальный момент он всегда находится в состоянии а₀. В момент времени t автомат воспринимает на входе букву входного алфавита z(t)ÎZ, находясь в состоянии a(t). В соответствии с функцией переходов автомат переходит в момент времени (t+1) в состояние a(t+1)= d(a(t), z(t)) и вырабатывает выходной сигнал z(t) в соответствии с функцией выходов: z(t)=l(a(t), z(t)) в случае автомата Мили, и z(t)=l(a(t)) в случае автомата Мура. Таким образом, автомат S отображает множество слов входного алфавита Z в множество слов выходного алфавита W.

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

Автомат называется конечным, если конечны множества A,Z,W. Далее мы будем рассматривать только конечные автоматы. Автомат называется полностью определенным, если он определен всюду на множестве A´Z. В противном случае автомат называется частичным.

Чтобы задать автомат, необходимо описать все компоненты вектора S=(A,Z,W,d,l, a₀), т.е. входной и выходной алфавиты, алфавит состояний, функции переходов и выходов. Для описания автомата наиболее часто используются табличный и графический способы задания. Наиболее удобны отмеченные таблицы переходов-выходов, Таблицы 17, 18.

Для частичных автоматов функции переходов и выходов определены не для всех пар (a_m,z_f). В клетке неопределенности ставится прочерк.

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

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

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

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

Перевод правильной дроби из кода Д1 в двоичную систему счисления

Перевод выполняется за n+1 такт, где n – число двоичных разрядов, обеспечивающих точность перевода такую же, как у исходного десятичного числа. Необходимое сило разрядов может быть определено из выражения

где k – число разрядов десятичного числа, определяющее его точность.

Чтобы определить алгоритм перевода числа из системы счисления с основанием q в систему счисления с основанием p, запишем числоA_q в виде разложения по степеням 2:

A_q=a₁p^-1+a₂p^-2+…+a_np^-n=p^-1(a₁+p^-1(a₂+…+p^-1(a_n+0))…).

(1)

Полученное выражение есть схема Горнера, определяющая последовательность действий при переводе.

Умножая A_q на p, получим смешанную дробь, целая часть которой будет равна первой цифре числа в системе счисления с основанием q. Далее, умножая дробную часть получившегося числа A^’_q на p, будем получать в целой части получающейся смешанной дроби значения очередных цифр в системе счисления с основанием р. При этом, если q>p, то цифры числа в новой системе счисления будут сразу получаться правильными. Если же p>q, то целая часть смешанной дроби, получающейся в результате умножения q-ичной правильной дроби на основание новой системы счисления будет представлять очередную цифру р-ичного числа кодовой последовательностью в q-ичной системе счисления. Из выражения (1) следует следующий алгоритм перевода правильной дроби из кода Д1 в двоичную систему счисления, представленный в табл. 1Примем значение исходного числа равным А₁₀=0.137₁₀. Число необходимых двоичных разрядов не меньше (3/lg2), т.е. больше или равно 10. Следовательно, необходимо принять число тактов равным 11 для последующего округления результата. В коде Д1 наше число будет иметь вид: А₁₀= 0001 0011 0111. Умножение на 2 соответствует сдвигу регистра, в котором хранится число А на один разряд влево. Исходное число в коде Д1 хранится в РгА, Двоичный код записывается в РгВ последовательно разряд за разрядом, начиная со старшего разряда, путем сдвига РгВ влево. В таблице, представляющей алгоритм перевода, будем также записывать результат умножения десятичного числа на 2 в десятичной системе счисления (столбец А₁₀), чтобы контролировать результат выполнения операций сдвига и коррекции в коде Д1. Таблица также содержит столбец СТ, в котором учитывается число уже выполненных тактов. Критерием завершения операции перевода является СТ=0.

Таблица 13 Перевод правильных дробей из кода Д1 в двоичную систему счисления

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

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

Коррекции в коде Д1 при сдвиге влево выполняются:

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

В любом случае коррекция в коде Д1 состоит в подсуммировании +6 к тетраде, требующей коррекции. При коррекции формируется символ переноса в старшую тетраду. Поэтому запись цифры из целой части дроби в коде Д1 в РгВ [10] следует производить после выполнения коррекции.