Определение чётности числа в уравновешенной троичной системе

[Shaos]

Вопрос а насколько надо знать чётное число или нет "мгновенно"?...

[Lavr]

Вопрос а насколько надо знать чётное число или нет "мгновенно"?...

Так это и есть вопрос, который я ранее задал: а нужен ли вобще флаг четности?

Я его учитывал просто как четность числа - удобно для алгоритмов типa: "на 1-й, 2-й рассчитайсь".

Классически четность, как четное или нечетное число единиц в слове, была введена для контроля
приёма-передачи информации.
Но потом аппаратно это стали делать сами БИС различных контроллеров и необходимость в этом флаге
перестала быть актуальной.

В принципе - один циклический сдвиг, типа RAL, и четность уже проверяется как флаг C в двоичности.

Поэтому я и задал тут вопрос, а нужен ли вобще флаг четности в троичном CPU?

[Lavr]

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

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

[Lavr]

Если в троичке и нужна "четность", то скорее в виде потритовой суммы трайта (этакое однотритовое подобие CRC)

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

К примеру, у популярного процессора 6502 никакого флага четности не было отродясь:

6502flags.gif

Но это всё двоичка, как говорится, "проехали"...

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

[JeNNeR]

Тут же как раз фокус в вычислении:
Сумма чисел четного числа (в троичной системе) является четным числом, меньшим, чем число.
В случае числа 2, сумма равна числу. То есть, каждое вычисление суммы просто сьедает лишние разряды.
Из большого числа типа PNNPPOONNPPNNOOPPNNOP(2'107'373'806) остается PNNP(16).
Из которого уже получаем PP(4), из которого получаем PN(2).
Если в конце получили 2, значит четное. Если хоть раз не получили - нечетное.

З.Ы. Кстати, сумма количества ненулевых разрядов штука нужная.
Наверняка понадобится для определения знака числа:
пока она больше 1/-1, сдвигаем вправо (делим на 3 с отбрасыванием). стала равна -1/0/1 = получаем знак числа.

[Lavr]

Кстати, сумма количества ненулевых разрядов штука нужная.
Наверняка понадобится для определения знака числа:

Знак числа аппаратно определяется довольно просто без подсчета ненулевых разрядов.
Хотя, конечно, сложнее, чем в двоичности...

Может быть, опять же при передаче данных сумма количества ненулевых разрядов может понадобиться

[petrenko]

Собственно вопрос плавно переходит в плоскость « Троичный "CRC" в кремнии . Как реализовать. И нужно ли ? »

[Shaos]

Давайте не будем путать чётность числа (делимость нацело на 2) и чётность количества единиц в его двоичном представлении (parity) - последнее возможно и нужно, но своё, троичное...

[Lavr]

А мы и не путаем, просто обсуждение так пошло сумбурно.

Топик же звучит как: "Определение чётности числа в уравновешенной троичной системе"
В процессоре возможен "флаг четности", вот я и решил посоветоваться с коллегами,
нужен ли в троичном процессоре "флаг четности", и что он должен отражать, если нужен.

А путать - тут никто ничего не путает.

[Shaos]

Ну началось всё как раз с чётности как признака делимости на 2 без остатка

Кстати если для определения чётности в троичной системе речь идёт о подсчёте ненулевых разрядов, то оно как бы само собой сливается с понятием "parity"

Тогда оно наверное таки надо - загоню задачку в DDT, посмотрим что оно нагородит

[Shaos]

Ну началось всё как раз с чётности как признака делимости на 2 без остатка

Кстати если для определения чётности в троичной системе речь идёт о подсчёте ненулевых разрядов, то оно как бы само собой сливается с понятием "parity"

Тогда оно наверное таки надо - загоню задачку в DDT, посмотрим что оно нагородит

Задаём вот такой входной DDT файл - par3.ddt:

Code: Select all

NNN=N
NNO=P
NNP=N
NON=P
NOO=N
NOP=P
NPN=N
NPO=P
NPP=N
ONN=P
ONO=N
ONP=P
OON=N
OOO=O
OOP=N
OPN=P
OPO=N
OPP=P
PNN=N
PNO=P
PNP=N
PON=P
POO=N
POP=P
PPN=N
PPO=P
PPP=N

N - нечётное
O - ноль
P - чётное

Далее пускаем ddtc par3.ddt и получаем на выходе ddt_par3.c:

Code: Select all

 
/* Generated by DDTc v0.5
   Solution is 6 x DG403
   See www.ternary.info */

#include "ddt.h"

int ddt_par3(int f, DDT i1, DDT i2, DDT i3, DDT* o1)
{
 DDT r1,r2,r3,r4,r5,r6;
 int f1,f2,f3,f4,f5,f6;
 f1 = ddt_mux(f,i1,N,P,N,&r1);
 if(f1 < 0) return f1;
 f2 = ddt_mux(f,i1,P,N,P,&r2);
 if(f2 < 0) return f2;
 f3 = ddt_mux(f,i1,N,O,N,&r3);
 if(f3 < 0) return f3;
 f4 = ddt_mux(f,i2,r1,r2,r1,&r4);
 if(f4 < 0) return f4;
 f5 = ddt_mux(f,i2,r2,r3,r2,&r5);
 if(f5 < 0) return f5;
 f6 = ddt_mux(f,i3,r4,r5,r4,&r6);
 if(f6 < 0) return f6;
 if(o1) *o1 = r6;
 return f1+f2+f3+f4+f5+f6;
}

Если считать, что OOO это всё-таки чётное число (P вместо O), то решение сокращается до 5 мультиплексоров:

Code: Select all

 
/* Generated by DDTc v0.5
   Solution is 6 x DG403
   See www.ternary.info */

#include "ddt.h"

int ddt_par3(int f, DDT i1, DDT i2, DDT i3, DDT* o1)
{
 DDT r1,r2,r3,r4,r5;
 int f1,f2,f3,f4,f5;
 f1 = ddt_mux(f,i1,N,P,N,&r1);
 if(f1 < 0) return f1;
 f2 = ddt_mux(f,i1,P,N,P,&r2);
 if(f2 < 0) return f2;
 f3 = ddt_mux(f,i2,r1,r2,r1,&r3);
 if(f3 < 0) return f3;
 f4 = ddt_mux(f,i2,r2,r1,r2,&r4);
 if(f4 < 0) return f4;
 f5 = ddt_mux(f,i3,r3,r4,r3,&r5);
 if(f5 < 0) return f5;
 if(o1) *o1 = r5;
 return f1+f2+f3+f4+f5;
}

[TernarySystem]

...для определения чётности числа: я бы по-разрядно сложил бы все числа троичного числа и суму сначала поделил бы на 3 если число поделилось на три без остатка затем поделил бы на 2 - если есть остаток то число нечётное, если же сума от деления на три имеет остаток то число есть нечётное и проверять делением на два ненужно.

[TernarySystem]

я бы по-разрядно сложил

Сложение на аппаратном уровне выглядит сложнее. Как минимум три мультиплексора на разряд.

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

[Shaos]

я бы по-разрядно сложил

Сложение на аппаратном уровне выглядит сложнее. Как минимум три мультиплексора на разряд.

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

Логисторы?

[Shaos]

Я вот больше по графике понимаю. А эти колонки цифр и буков в головушке моей не укладываются.
З.Ы. У меня тоже 5 получается для трёх разрядов.

вот так с нулём получается:

Parity3.png

это я в логисиме вручную перерисовал чего DDT нагенерил - надо уже доделать ddtv, которая будет визуализировать троичные схемы на мультиплексорах

P.S. без нуля (ноль - чётное) выкидывается мультиплексор r3, мультиплексоры r4,r5 и r6 переименовываются в r3,r4 и r5, а средний вход нового r4 (старого r3) цепляется к выходу r1