VI Международная студенческая научная конференция Студенческий научный форум - 2014

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

Троичная система счисления - позиционная целочисленная система счисленияс основанием 3. Существует в двух вариантах: несимметричная (цифры 0, 1, 2) и симметричная (цифры -1, 0, 1). В данной статье пойдет речь о моделировании алгоритмов сложения, вычитания, умножения и деления чисел в троичной несимметричной системе счисления на двоичных элементах. В статье приведены исходные коды описанных алгоритмов на языке C++.

Один троичный разряд можно представить двумя двоичными разрядами,при этом введем следующее соответствие между двоичными и троичными числами:двоичная комбинация 00 соответствует троичному нулю, 10 - единице, 01 - минус единице, а комбинация 11 является недопустимой.

Одноразрядный троичный сумматор вычисляет разряд суммы sи перенос p₁в следующий разряд для двух троичныхразрядов aи b, с учетом переноса из предыдущего разрядаp₀.  Правила работы одноразрядного троичного сумматора представлены в таблице 1.

a	b	p0	s	p1		a	b	p0	s	p1		a	b	p0	s	p1
00	00	00	00	00		00	00	01	01	00		00	00	10	10	00
00	01	00	01	00		00	01	01	10	01		00	01	10	00	00
00	10	00	10	00		00	10	01	00	00		00	10	10	01	10
01	00	00	01	00		01	00	01	10	01		01	00	10	00	00
01	01	00	10	01		01	01	01	00	01		01	01	10	01	00
01	10	00	00	00		01	10	01	01	00		01	10	10	10	00
10	00	00	10	00		10	00	01	00	00		10	00	10	01	10
10	01	00	00	00		10	01	01	01	00		10	01	10	10	00
10	10	00	01	10		10	10	01	10	00		10	10	10	00	10

 

Таблица 1. Правила работы одноразрядного троичного сумматора.

Программная реализация одноразрядного сумматора приведена в листинге 1. В подпрограмме sum1 используется обозначение TTritдля реализации троичного разряда в виде класса с функциями доступа к двоичным разрядам (0 - младший, 1 - старший), а также сравнения и присвоения (обозначение операторов аналогично  обозначению соответствующих операторов в языке C++).

voidsum1(constTTrit&a, constTTrit&b, constTTrit&p0, TTrit&s,

TTrit&p1) {

bool a1=a[1], a0=a[0], b1=b[1], b0=b[0], p01=p0[1], p00=p0[0];

  s[1] = !a1&&!a0&&b1&&!b0&&!p01&&!p00 || !a1&&a0&&!b1&&b0&&!p01&&!p00 ||

    a1&&!a0&&!b1&&!b0&&!p01&&!p00 || !a1&&!a0&&!b1&&b0&&!p01&&p00 ||

    !a1&&a0&&!b1&&!b0&&!p01&&p00 || a1&&!a0&&b1&&!b0&&!p01&&p00 ||

    !a1&&!a0&&!b1&&!b0&&p01&&!p00 || !a1&&a0&&b1&&!b0&&p01&&!p00 ||

    a1&&!a0&&!b1&&b0&&p01&&!p00;

  s[0] = !a1&&!a0&&!b1&&b0&&!p01&&!p00 || !a1&&a0&&!b1&&!b0&&!p01&&!p00 ||

    a1&&!a0&&b1&&!b0&&!p01&&!p00 || !a1&&!a0&&!b1&&!b0&&!p01&&p00 ||

    !a1&&a0&&b1&&!b0&&!p01&&p00 || a1&&!a0&&!b1&&b0&&!p01&&p00 ||

    !a1&&!a0&&b1&&!b0&&p01&&!p00 || !a1&&a0&&!b1&&b0&&p01&&!p00 ||

    a1&&!a0&&!b1&&!b0&&p01&&!p00;

p1[1] = a1&&!a0&&b1&&!b0&&!p01&&!p00 || !a1&&!a0&&b1&&!b0&&p01&&!p00 ||

    a1&&!a0&&!b1&&!b0&&p01&&!p00 || a1&&!a0&&b1&&!b0&&p01&&!p00;

p1[0] = !a1&&a0&&!b1&&b0&&!p01&&!p00 || !a1&&!a0&&!b1&&b0&&!p01&&p00 ||

    !a1&&a0&&!b1&&!b0&&!p01&&p00 || !a1&&a0&&!b1&&b0&&!p01&&p00;

}

Листинг 1. Программная реализация одноразрядного сумматора.

Сложение N-разрядных троичных чисел заключается в последовательном использовании  одноразрядного сумматора для каждого разряда слагаемых, начиная с младшего (листинг 2).

void add(constTTernary&a, constTTernary&b, TTernary&c) {

TTrit p0, p1;

for(int i = 0; i < N; i++) {

sum1(a[i], b[i], p0, c[i], p1);

    p0 = p1;

}

}

Листинг 2. Программная реализация N-разрядного троичного сумматора.

 

В листинге 2 используются следующие обозначения: a и b - слагаемые, c - сумма, p0 - перенос в текущий разряд, p1 - перенос в следующий разряд, TTernary - реализация N-разрядного троичного числа в виде класса с функциями доступа к троичным разрядам, а также сравнения, присвоения и сдвига.

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

 

void sub(constTTernary&a, constTTernary&b, TTernary&c) {

TTernary b2;

for(int i = 0; i < N; i++) {

if(b[i] == "10") b2[i] = "01";

else if(b[i] == "01") b2[i] = "10";

  }

add(a, b2, c);

}

Листинг 3. Программная реализация N-разрядного троичноговычитателя.

В листинге 3 используются обозначения: a-уменьшаемое, b-вычитаемое, c-разность, b2 -вычитаемое в троичной инверсии.

Умножение троичных чисел (листинг 4) выполняется в цикле, на каждом шаге которого анализируется младший разряд множителя: умножение на 10 увеличивает частичное произведение на величину множимого, умножение на 01 - уменьшает на такую же величину. Затем множимое сдвигается на 1 разряд влево, а множитель - на 1 разряд вправо. Если перед выполнением очередного шага множитель равен нулю, то необходимо закончить умножение.

voidmult(constTTernary&a, constTTernary&b, TTernary&c) {

TTernary x = TTernary(a), y = TTernary(b);

  c = 0;

while(y != 0) {

if( y[0] == "10" ) add(c, x, c);

else if( y[0] == "01" ) sub(c, x, c);

    x <<= 1;

    y >>= 1;

  }

}

Листинг 4. Программная реализация троичного умножителя.

В листинге 4 использованы следующие обозначения: a, x - множимое, b, y - множитель, c - произведение.

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

void div(constTTernary&a, constTTernary&b, TTernary&c) {

TTernaryaa, r, r2;

add(a, a, aa);

  c = 0;

for(int i = N-1; i >= 0; i--) {

    r <<= 1;

r[0] = aa[N-1];

aa<<= 1;

if( r >= 0 ) {

sub(r, b, r2);

if( (r2 > 0) || ((r2 == 0) && (aa> 0)) ) {

c[i] = "10";

sub(r2, b, r);

      }

    } else {

add(r, b, r2);

if( (r2 < 0) || ((r2 == 0) && (aa< 0)) ) {

c[i] = "01";

add(r2, b, r);

      }

    }

  }

}

Листинг 5. Программная реализация делителя троичных чисел.

В листинге 5 использованы следующие обозначения: a-делимое, b-делитель, c-частное, aa-удвоенное делимое, r-остаток (удвоенный).

 

Список литературы

1.     РамильАльварес Х. Алгоритмы деления и извлечения квадратного корня в троичной симметричной системе // Вестн. Моск. ун-та. Сер. 15. Вычислительная математика и кибернетика. 2008. № 2. С. 42-45.

2.     Фомин С. В. Системы счисления. - М.: Наука, 1987. 

Код для цитирования: Скопировать