О 19683 троичных элементах

nabbla1 — 23.10.2025 Несколько раз упоминал это страшное число. Двоичных логических элементов с 2 входами и 1 выходом может быть всего 16 разных, причём половина "вырожденные" (константы 0 и 1, либо один вход не задействован), так что всем оставшимся можно дать имена и перечислить их буквально на пальцах.

А стоит попробовать пересчитать все возможные троичные логические элементы с теми же 2 входами и 1 выходом - их выйдет 19683, тут вообще не ясно было, как подступиться.

Но на днях додумался взглянуть на это дело чуть с другой стороны. Стал думать о том, а для чего в программах чаще всего используются именно что ЛОГИЧЕСКИЕ операции AND, OR, XOR. Как правило, это устанавливаются, сбрасываются и проверяются отдельные биты ("флаги") из слова. И тогда можно сказать следующее: МЫ ЗАГОТАВЛИВАЕМ 2 УНАРНЫЕ ОПЕРАЦИИ НАД БИТОМ, И В ЗАВИСИМОСТИ ОТ БИТА МАСКИ ВЫБИРАЕМ ОДНУ ИЗ НИХ.




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


Нечто подобное применяется внутри ПЛИС: вместо функции от 4 входов (LUT4) там, на самом деле, применено две фукнкции от 3 входов (LUT3), и в "обычном режиме" четвёртый вход определяет, какую из двух функций выбрать. Зато в арифметическом режиме первая функция используется для получения текущего бита (младший бит при сложении A+B+carry, например), а вторая - для получения переноса.

Ещё родственное понятие - каррирование функций, где из выражения (к примеру) A+B можно отдельно выделить A+, т.е "применить плюс к одному числу", результатом чего станет функция, т.е 2+ - это функция, которая к своему аргументу прибавляет 2. И тогда A+B - это то же самое, как функция (A+), применённая к аргументу B. Впрочем, в эту сторону закапываться пока не будем, мы сейчас немного не об этом.

Если вспомнить, что унарных операций над битами существует всего 4:
- "константа 0" (выдавать на выходе 0 независимо от входа),
- "константа 1",
- повторитель/буфер (выход = входу),
- инвертор (сменить 0 на 1, а 1 сменить на 0),

и можно независимо выбрать "первую" и "вторую" унарную операцию, то у нас получается 4·4 = 16 различных бинарных операций.

И тот же принцип можно распространить на троичную логику. Функция от 2 тритов - это то же самое, как ТРИ УНАРНЫХ ФУНКЦИИ над одним и тем же входом и мультиплексор, управляемый вторым входом, который выбирает один из трёх выходов.

Прелесть в том, что 27 унарных функций мы успешно классифицировали!

И да, имея возможность выбрать одну из 27 функций ТРИЖДЫ, мы и получаем 27³ = 19683 различных функции! Надеюсь, так "комбинаторный взрыв" (как мы от 16 перешли к 19683) представить чуть проще, всё-таки многообразие унарных элементов куда богаче в троичной логике, хоть и вполне обозримо.

Можно поразмышлять, как будут выглядеть "тритовые маски" в таких компьютерах. Скорее всего, одно значение (0) мы оставим под то, чтобы "ничего не трогать", оставить трит в слове как он есть. И ещё мы можем сделать над ним два других действия. Например, "установить" в 1, либо "сбросить" в -1.

Обычный AND, "переделанный в троичный" (см троичные И-НЕ - первый успех!), может "сбросить в -1" (если в маске задать "-1"), может "оставить как есть" (если задать "1"), либо при задании "0" это будет "не более 0", т.е "-1" и "0" останутся как есть, а вот "1" превратится в "0". В общем-то, логично: AND(A,B) = MIN(A,B), такое соотношение действует и в двоичном, и в троичном случае! И, симметрично, OR(A,B) = MAX(A,B). Оно даже в "нечёткую логику" простирается.

Базовый элемент для троичной арифметики, младший разряд полусумматора, является совокупностью (дипломат, генерал, девушка). Т.е если второй вход нулевой - оставляем как есть (генерал). Второй вход "-1" - включаем "дипломата", на первом входе "ДА" (1), подразумеваем "МОЖЕТ БЫТЬ" (0), а "МОЖЕТ БЫТЬ (0)" подразумеваем "НЕТ" (-1). Наконец, второй вход "+1" - включаем "девушку".

Возникает уверенность, что и произвольный троичный логический элемент с 3 входами может быть синтезирован "малой кровью". Конечно, памятуя о ПЛИС, можно было бы и здесь тупо использовать таблицу истинности, и сразу видно: она представляется 9 тритами, ничего сильно злого. Но теперь становится видно, что и "на голом железе" оно нормально выйдет. Как синтезировать каждый унарный элемент - мы фактически рассмотрели. А вместо "отдельного мультиплексора" мы можем цепочки, "тянущие вверх" и "тянущие вниз", от всех 3 унарных функций пустить параллельно, не забыв снабдить каждую ещё одним транзистором "разрешения работы".

Можно и тут немного попробовать поклассифицировать:

1. все 3 унарные функции выбраны одинаковыми. Тогда у нас просто нет зависимости от входа B, т.е наш элемент сам является унарным, и таких ровно 27 штук, их мы уже все перечислили. Осталось разобраться с другими 19656.

2. используется 2 разные унарные функции. Можно выбрать одну из 27 унарных функцию для f1, и ещё одну из 26 для f2 (чтобы не прийти к пункту 1, где все 3 одинаковые), что даёт 702 варианта. Но ещё можно выбрать, что f1 выполняется для B=-1, либо для B=0, либо для B=1, а f2 выполняется в противном случае. Т.е количество вариантов ещё умножается на 3, что даёт 2106 вариантов. Это у нас некая помесь - функция с двоичным и троичным входом. Вообще, может быть полезно. А всего рассмотрено 2133 элемента, осталось 17550.

3. все 3 унарные функции разные. Выбираем одну из 27 для B="-1", затем одну из 26 для B="0" и одну из 25 для B="1". Всего выходит 27*26*25 = 17550 вариантов. Сошлось! Но при этом будет получаться "концептуально" похожие логические элементы, отличающиеся лишь интерпретацией входа B. Т.е эти элементы будут переходить друг в друга, если вход B предварительно прогнать через один из 6 "перестановочных" унарных элементов. Тогда "уникальных" логических элементов выходит в 3!=6 раз меньше, а именно: 2925 штук. Конечно, всё равно много, но не МНОГО-МНОГО...


Надеюсь в скором времени вернуться к макетированию компонентов троичного вычислителя. Хочется ещё разок "всё начать по-новой": идея варьирования напряжения подложки 176ЛП1 меня разочаровала, верхние транзисторы очень туго на это реагируют, не удаётся далеко увести пороги открывания, не превысив напряжения, ещё и часть транзисторов станет пропадать впустую, т.к их исток с подложкой уже соединены внутри корпуса ЛП1. Кажется, есть способ сильно проще - варьировать напряжение на ИСТОКЕ, легко и непринуждённо. Как только устаканится базовая логика - хочу вообще "конструктор" себе сделать, что-то вроде "модульного синтезатора" - вставляешь отдельные платки, чтобы на них пришло питание и тактовая частота, а потом сверху соединяешь их между собой, чтобы построить ту или иную логику.

Оставить комментарий

Популярные посты:

• Архив