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

Цель исследования. Формализация полного математического аппарата Новой системы счисления Фибоначчи (NFNS), построенной на базе авторского правила ограничения четностей (Voron’s parity constraint rule), и проектирование эффективной микроэлектронной архитектуры основных вычислительных узлов для построения отказоустойчивых процессоров нового поколения.

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

Результаты исследования. Впервые осуществлено строгое теоретико-множественное описание статического и динамического алфавитов системы NFNS, а также грамматики регулярного языка разрешенных кодовых последовательностей. Разработан и математически формализован алгоритм параллельно-локального поразрядного вычитания (заёма разрядов) с разделением логики для четных и нечетных индексов, а также предложена концепция модифицированного знакового разряда (Sign-Parity Bit). Выведена комбинаторная формула информационной емкости разрядной сетки, доказавшая константный характер избыточности системы NFNS (ровно 1 дополнительный бит на числовое слово). Предложено расширение системы в область вещественных чисел посредством введения знаковой негафибоначчиевой последовательности весов разрядов сквозь позиционную запятую. На уровне аппаратной логики спроектирована схема комбинационного автомата предсказания синтаксиса (Look-Ahead Constraint Automata) с константным временем стабилизации сигналов (O(1) по тактам). Разработан алгоритм возведения в степень (Power Algorithm NFNS), использующий тождества Кассини и д'Оканя для ликвидации тяжелых матричных вычислений и обеспечивающий аппаратную защиту криптопроцессоров от атак по сторонним каналам.

Практическая значимость. Предложенный математический аппарат и логическая структура АЛУ позволяют отказаться от сложных внешних кодов проверки (коды Хемминга, ECC) и схем тройного модулирования (TMR), обеспечивая абсолютный иммунитет к радиационным сбоям и ликвидацию проблемы сквозного лавинного переноса при минимальных затратах площади кремниевого кристалла.

Ключевые слова: новая система счисления Фибоначчи, NFNS, алфавит системы, поразрядный заём, Look-Ahead автомат, негафибоначчиевы разряды, модульное возведение в степень, помехоустойчивость АЛУ, дуальный базис.

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

В рамках традиционной двоичной архитектуры ЭВМ данные задачи вступают в жесткое диалектическое противоречие. С одной стороны, параллельная обработка данных в двоичных сумматорах ограничена проблемой сквозного лавинного переноса битов (carry propagation), требующей для своего парирования построения громоздких многоярусных схем ускоренного переноса, увеличивающих площадь кристалла и энергопотребление. С другой стороны, классический двоичный код обладает фундаментальным дефектом – нулевой избыточностью. Любое физическое искажение структуры данных, вызванное эффектом SEU (Single-Event Upsets или «бит-флип»), мгновенно и латентно трансформирует один легитимный кодовый вектор в другой, порождая скрытые критические отказы системы вычислений. Существующие инженерные методы защиты, такие как программно-аппаратный контроль памяти кодами Хемминга (ECC) или схемы тройного модулирования (TMR) с мажоритарным голосованием, приводят к утяжелению аппаратуры, снижению ее тактовой частоты и росту физической площади полупроводникового кристалла на 200–300%.

Фундаментальная альтернатива двоичной парадигме была заложена в середине 1970-х годов в трудах д.т.н., профессора А.П. Стахова, разработавшего компьютерную арифметику Фибоначчи и выдвинувшего концепцию «компьютеров Фибоначчи» [2, 3, 4]. Фибоначчиевые позиционные системы счисления обладают врожденной помехоустойчивостью и способностью к мгновенному обнаружению сбоев «на лету» непосредственно на уровне математического кода за счет системы синтаксически запрещенных состояний (в частности, запрета Цекендорфа на смежное появление двух единиц …11…) [1].

Тем не менее, широкое коммерческое внедрение классической фибоначчиевой арифметики А.П. Стахова в микроэлектронную индустрию столкнулось с серьезными инженерно-технологическими барьерами:

1. Неравномерная и бесконечная избыточность. Уровень многозначности представления чисел в фибоначчиевом коде динамически и хаотически изменяется для различных участков натурального ряда, порождая так называемый «эффект нуля».

2. Вычислительная сложность стабилизации. Архитектура А.П. Стахова требует непрерывного выполнения ресурсоемких многотактных локальных операций свертки (011→ 100) и развертки (100→011) по всей длине числового слова. Данный процесс вызывает каскадный «эффект домино», ухудшает временные характеристики АЛУ и нивелирует преимущества параллельной обработки.

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

С целью преодоления указанных недостатков автором была разработана Новая система счисления Фибоначчи (New Fibonacci Numeral System, NFNS), теоретический базис которой подробно изложен в работах [5, 6, 7, 8, 9]. В основу NFNS положено математическое ограничение нового типа – Правило ограничения четностей (Voron’s parity constraint rule / Position parity-based NFNS), которое запрещает нахождение активных разрядов («1») в смежных позициях одинаковой четности и накладывает строгий синтаксический запрет на бинарные последовательности, содержащие последовательное нечетное количество знаков «0» между единицами. Сформулированная на основе данного правила теорема Ворона о дуальном базисе показывает, что кодирование любого натурального числа в системе NFNS сводится к строго дуальной (двухвариантной – рабочей и контрольной) форме, полностью ликвидируя бесконечную избыточность стандартного фибоначчиева кода.

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

Настоящая работа посвящена решению следующих задач, составляющих ядро завершенной теории NFNS:

1. Строгая теоретико-автоматная формализация алфавитов и грамматики регулярного языка NFNS.

2. Математическое описание и построение алгоритма поразрядного вычитания (заёма разрядов) и знаковой арифметики в дуальном базисе.

3. Комбинаторная оценка информационной емкости разрядной сетки и расчет константного коэффициента избыточности.

4. Масштабирование правила Ворона на область непрерывных (вещественных) вычислений с фиксированной и плавающей запятой на основе знакового негафибоначчиевого ряда весов.

5. Логическое проектирование комбинационной схемы и графа переходов автомата синтаксической фильтрации с параллельным блоком просмотра вперед (Look-Ahead Constraint Automata).

6. Разработка квазимультипликативного алгоритма возведения в степень на основе алгебраических тождеств произведений (тождеств Кассини и д'Оканя) для высокозащищенных криптографических приложений.

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

Для строгого математического описания Новой системы счисления Фибоначчи (NFNS) необходимо формализовать структуру её алфавитов и синтаксические правила, определяющие допустимость кодовых комбинаций. В отличие от традиционных позиционных систем, где валидность слова W проверяется исключительно поразрядной принадлежностью символов алфавиту, в NFNS ключевую роль играет позиционно-грамматический контекст.

формате PDF (416Кб)