"Фибоначчиевый" регистр для операции "свертки"

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

В качестве основы для устройства "свертки" может выбранный классический двоичный регистр, состоящий из триггеров. Этот регистр имеет специальные логические схемы для выполнения операций "свертки". Каждая разряд регистра содержит Т-триггер и логические элементы. Операция "свертки" (011 ® 100) может быть представлена как инверсия состояний соответствующих триггеров. Инверсия состояния триггера выполняется очень легко для триггера с "установочным" и "счетным" входами.

Один из возможных вариантов регистра "свертки" показан на Рис.1. Регистр "свертки" состоит из пяти R-S-триггеров и логических элементов AND, OR (И, ИЛИ), которые предназначены для реализации "свертки". Операция "свертки" выполнятся, начиная с младшего триггера T1 к старшему триггеру T5 с помощью логических элементов AND1 - AND5 и соответствующих логических элементов OR (ИЛИ), расположенных перед R- и C -входами соответствующих триггеров. Логический элемент AND1 реализует "свертку" 1-го разряда во 2-й разряд регистра. Его два входа связаны с прямым выходом триггера T1 и "инверсным" выходом триггера T2. Его 3-й вход связан с сигналом синхронизации C. Логический элемент AND1 анализирует состояния Q1 и Q2 триггеров T1 и T2. Если Q1 = 1 и Q2 = 0, это означает, что условие "свертки" для 1-го и 2-го разрядов выполняется. Синхросигнал C = 1 является причиной появления логический 1 на выходе элемента AND1. Эта логическая 1 вызывает переключение триггеров T1 и T2 в противоположное состояние. Это приводит к выполнению операции "свертки" над первыми двумя разрядами регистра.

Логический элемент ANDk k-го разряда (k = 2, 3, 4, 5) реализует операцию "свертки" (k - 1)-го и k-го разрядов в (k + 1)-й разряд. Его три входа связаны с "прямыми" выходами триггеров Tk-1 и Tk и "инверсным" выходом триггера Tk+1. 4-й вход связан с синхросигналом C. Логический элемент ANDk анализирует состояния Qk-1, Qk и Qk+1 триггеров Tk-1, Tk и Tk+1. Если Qk-1 = 1, Qk = 1 и Qk+1 = 0, это означает, что условие "свертки" выполняется. Синхросигнал C = 1 приводит к переключению триггеров Tk-1, Tk, and Tk+1. При этом выполняется операция "свертки" над соответствующими разрядами (011 ® 100).

Заметим, что все элементы AND1 - AND5 связаны через общий логический элемент ORc с контрольным выходом регистра "свертки".

Регистр "свертки" на Рис.1 работает следующим образом. Входная кодовая информация поступает на входы 1 - 5 регистра "свертки" и далее поступает на S-входы триггеров через соответствующие логические элементы OR.

'Фибоначчиев' регистр 'свертки'

Рисунок 1. "Фибоначчиев" регистр "свертки".

Пусть исходное состояние регистра "свертки" следующее:

5 4 3 2 1
0 1 0 1 1

Ясно, что условие "свертки" выполняется только для 1-го, 2-го и 3-го разрядов. Синхросигнал C = 1 приводит к переходу регистра "свертки" в следующее состояние:

5 4 3 2 1
0 1 1 0 0.

Здесь условие "свертки" выполняется только для 3-го, 4-го и 5-го разрядов. Очередной синхросигнал C = 1 приводит к переходу регистра "свертки"в следующее состояние:

5 4 3 2 1
1 0 0 0 0.

"Свертка" исходной кодовой комбинации 0 1 0 1 1 закончилась.

Регистр "свертки" в Фибоначчи-процессоре играет важную роль самоконторлирующегося устройства. Рассмотрим регистр "свертки" на Рис. 1 с этой точки зрения. Выходы логических элементов AND1 - AND5 регистра "свертки" на Рис.1 связаны с контрольным выходом регистра через общий логический элемент OR. Этот выход играет важную роль контрольного выхода регистра.

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

Интересно подчеркнуть, что схема на Рис.1 является необычной схемой, несмотря на ее кажущуюся простоту. Она признана изобретением пионерного характера во многих странах, включая США, Японию, Англию, Германию, Францию и Канаду.