Устройство управляемого циклического сдвига



Устройство управляемого циклического сдвига
Устройство управляемого циклического сдвига
Устройство управляемого циклического сдвига

 


Владельцы патента RU 2419174:

Государственное образовательное учреждение высшего профессионального образования "Саратовский государственный университет им. Н.Г. Чернышевского" (RU)

Устройство относится к области кодирования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является обеспечение возможности высокоскоростного циклического сдвига информации на m позиций за один такт внешнего генератора тактовой частоты. Устройство управляемого циклического сдвига содержит n входов данных, n выходов данных, m≤log2n битовых входов управляющего кода и входа тактовых импульсов, входного регистра данных с n входами данных, образующими входы данных устройства, входом тактовых импульсов электрически соединенным с входом тактовых импульсов устройства, при этом входной регистр n выходами данных электрически соединен с входами коммутационной матрицы, образованной переключателями, расположенными по n линиям и m уровням и имеющими битовый вход управляющего сигнала, первый и второй входы данных и выход данных. 3 ил.

 

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

Известен реверсивный регистр сдвига (далее объект), приведенный в книге С.А.Майорова и Г.И.Новикова Принципы организации цифровых машин, изд. «Машиностроение», Ленинград 1974, стр.127-132, рис.4.23. Указанный объект выполняет элементарные операции (ЭО) сдвига кода в сторону младших разрядов (вправо) и в сторону старших разрядов (влево) на один разряд за два временных такта. (Под тактом понимается длительность импульсов пересылки кода из основного регистра в вспомогательный и из вспомогательного снова в основной регистр со сдвигом на один разряд). Этот объект также требует двух RS-триггеров на каждый двоичный разряд, шесть элементов И, двух элементов ИЛИ и трех шин управления. Кроме сравнительно больших аппаратурных затрат, упомянутый объект выполняет только две ЭО. Выполнение каждой дополнительной операции требует увеличения оборудования каждого разряда на два элемента И и еще одной шины управления.

Данный регистр можно использовать для осуществления циклического сдвига информации.

Недостатком данного решения являются значительные потери времени при последовательном сдвиге информации на несколько позиций. Если τ - время задержки сдвига информации на одну позицию, то сдвиг на m позиций приводит к задержке на m·τ, которая растет пропорционально m, причем время задержки не постоянно, а пропорционально m.

Известен регистр сдвига (см. авт.св. СССР №1049978, МПК G11C 19/00), состоящий из N разрядов, где N≥3, и содержащий в каждом разряде JK-триггер и элемент "И". Выход триггера N-го разряда, где N=1, 2, …, N-1, подключен к информационному входу триггера N+1-го разряда. Тактовые входы триггеров всех разрядов объединены и являются тактовым входом регистра сдвига. Регистр сдвига выполняет функции сдвига и сжатия информации.

Данный регистр можно использовать для осуществления циклического сдвига информации.

Недостатком данного решения являются значительные потери времени при последовательном сдвиге информации на несколько позиций. Если τ - время задержки сдвига информации на одну позицию, то сдвиг на m позиций приводит к задержке на m·τ, которая растет пропорционально m, причем время задержки не постоянно, а пропорционально m.

Известен сдвигающий регистр (см. авт.св. СССР №1049978, МПК G11C 19/00), выполненный на элементах И, ИЛИ, НЕ, содержащий в каждом разряде первый и второй RS-триггеры, четыре элемента И, один элемент ИЛИ, информационный вход, первую и вторую шины управления приемом кода в первый и второй триггеры при выполнении операции сдвига кода, информационный выход, при этом выходы первого и третьего элементов И соединены с R-входами первого и второго RS-триггеров соответственно, выход второго элемента И подключен к первому входу первого элемента ИЛИ, второй вход которого соединен с информационным входом, а выход упомянутого элемента ИЛИ подключен к S-входу первого триггера, первые входы первого и второго элементов И связаны с первой шиной управления приемом кода в первый триггер, первые входы третьего и четвертого элементов И соединены с второй шиной управления приемом кода во второй триггер, отличающийся тем, что нулевой и единичный выходы первого триггера i-го разряда соединены с вторыми входами третьего и четвертого элементов И (i+1)-гo разряда соответственно, нулевой и единичный выходы второго триггера i-го разряда соединены с вторыми входами первого и второго элементов И (i+1)-гo разряда соответственно, кроме того, введен второй элемент ИЛИ, первый и второй входы которого соединены с S-входами первого и второго триггеров, выход упомянутого элемента ИЛИ является информационным выходом i-го разряда. Нулевой и единичный выходы первого триггера самого старшего разряда регистра соединены с первыми входами третьего и четвертого элементов И самого младшего разряда соответственно, третий вход четвертого элемента И подключен к входу управления операций циклического сдвига, нулевой и единичный выходы второго триггера самого старшего разряда соединены с вторыми входами первого и второго элементов И первого разряда соответственно, третий вход второго элемента И соединен с входом управления операцией циклического сдвига.

Данный регистр можно использовать для осуществления циклического сдвига информации.

Недостатком данного решения являются значительные потери времени при последовательном сдвиге информации на несколько позиций. Если τ - время задержки сдвига информации на одну позицию, то сдвиг на m позиций приводит к задержке на m·τ, которая растет пропорционально m, причем время задержки не постоянно, а пропорционально m.

Наиболее близким по функциональным свойствам является однотактный управляемый блок циклического сдвига, описанный в работах (1 - Гуц Н.Д., Молдовян А.А., Молдовян Н.А. Построение управляемых блоков перестановок с заданными свойствами // Материалы Международной конференции РусКрипто'2001. С.1-17; 2 - Молдовян Н.А., Молдовян А.А., Алексеев Л.Е. Перспективы разработки скоростных шифров на основе управляемых перестановок // Вопросы защиты информации, 1999, N1, с.41-47.). Блок состоит из входной и выходной шин, образующих вертикальные и горизонтальные линии, дешифратора, формирующего сигналы управления ключами, в местах пересечения входной и выходной шин установлены ключи, обозначенные символом, которые замыкают или размыкают цепь в зависимости от того, какой сигнал подается на вход управления ключом. Ключи замыкают цепь при значении управляющего сигнала, равного единице, при этом если а - значение входного бита информации, b - выходного, а τ - управляющего, то работа ключа соответствует формуле: b=ar. Соответственно, значения на выходе блока циклического сдвига определяются формулой:, где j=0, 1, … 2k-1. Дешифратор для конкретного значения управляющего кода вырабатывает единичный сигнал только на одном управляющем выходе дешифратора (например, с номером s=u1+2u2…+2m-1um), поэтому значения на выходе блока циклического сдвига имеют вид: bj=a(s+j)mod nrs=a(j+s)mod n или bj=ai, где j=(i-r)modn и r=s. Сложность реализации схемы оценивается количеством используемых ключей, которое равно n2. Главным достоинством данного решения является выполнение операции циклического сдвига с постоянным временем задержки (один такт), независимо от разрядности информационного блока. Заметим, что задержка в дешифраторе, связанная с формированием управляющих сигналов, зависит от конкретной реализации схемы блока управляемых перестановок. В большинстве случаев можно осуществить одновременное поступление управляющих сигналов на все дешифраторы и, следовательно, в этом случае время задержки не зависит от числа уровней.

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

Недостатком данного решения является аппаратная сложность реализации регистра, которая растет пропорционально n2, где n - длина регистра.

Задачей настоящего решения является упрощение аппаратной сложности устройства управляемого циклического сдвига при сохранении возможности сдвига информации на m позиций за один такт внешнего генератора тактовой частоты.

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

Поставленная задача достигается тем, что устройство управляемого циклического сдвига согласно изобретению содержит n входов данных, n выходов данных, m≤log2n битовых входов управляющего кода и входа тактовых импульсов, входного регистра данных с n входами данных, образующими входы данных устройства, входом тактовых импульсов электрически соединенным с входом тактовых импульсов устройства, при этом входной регистр n выходами данных электрически соединен с входами коммутационной матрицы, образованной переключателями, расположенными по n линиям и m уровням и имеющими битовый вход управляющего сигнала, первый и второй входы данных и выход данных, причем при подаче на битовый вход управляющего сигнала с низким логическим уровнем переключатель соединяет первый вход с выходом, а при подаче на битовый вход управляющего сигнала с высоким логическим уровнем переключатель соединяет второй вход с выходом, матрица n выходами данных электрически соединена с входами данных выходного регистра данных, имеющего вход тактовых импульсов, который электрически соединен с входом тактовых импульсов устройства, выходы данных выходного регистра образуют выходы данных устройства, выходы переключателей первого уровня образуют выходы матрицы, входы переключателей последнего уровня m образуют входы матрицы, каждый выход с номером i входного регистра данных электрически соединен с первым входом переключателя с номером i уровня m и со вторым входом переключателя с номером k, причем k=i+2m-lmod(n), где 2m-1mod(n) - остаток от деления 2m-1 на n, каждый выход переключателя с номером i уровня 1<j<m электрически соединен с первым входом переключателя с номером i предыдущего уровня j-1 и со вторым входом переключателя с номером k предыдущего уровня j-1, причем k=i+2j-1mod(n), где 2j-lmod(n) - остаток от деления 2j-1 на n, каждый выход переключателя с номером i первого уровня электрически соединен с входом данных с номером i выходного регистра данных, управляющие входы переключателей каждого уровня j электрически соединены между собой и с j-м выходом регистра кода, причем регистр кода имеет вход тактовых импульсов, электрически соединенный с входом тактовых импульсов устройства, и битовые входы управляющего кода устройства образованы m входами регистра кода.

Изобретение поясняется чертежами, где на фиг.1 приведена логическая схема устройства управляемого циклического сдвига для n=8, на фиг.2 приведена диаграмма орграфа, иллюстрирующая работу устройства для n=8, на фиг.3 приведена диаграмма орграфа, иллюстрирующая работу устройства для n=7, где

1. входной регистр данных;

2. выходной регистр данных;

3. регистр кода;

- Т11, Т21 Т31, T41, T51, Т61, T71, T81 - переключатели первого уровня коммутационной матрицы;

- T12, T22, Т32, Т42, Т52, Т62, Т72, T82 - переключатели второго уровня коммутационной матрицы;

- T13, Т23, Т33, Т43, Т53, Т63, Т73, Т83 - переключатели третьего уровня коммутационной матрицы;

- D1-D8 - входы данных устройства и входного регистра данных;

- Q1-Q8 - выходы данных устройства и выходного регистра данных;

- QS1-QS8 - выходы входного регистра данных;

- DS1-DS8 - входы выходного регистра данных;

- clk - вход тактовых импульсов;

- j=1, j=2, j=3 - первый, второй и третий уровни коммутационной матрицы;

- X1, X2 - первый и второй входы переключателя;

- Y - выход переключателя;

- С - управляющий вход переключателя;

- С1 - вход первого бита кода управления сдвигом устройства и регистра кодов;

- С2 - вход второго бита кода управления сдвигом устройства и регистра кодов;

- С3 - вход третьего бита кода управления сдвигом устройства и регистра кодов;

- S1 - выход первого бита управления регистра кодов;

- S2 - выход второго бита управления регистра кодов;

- S3 - выход третьего бита управления регистра кодов.

Устройство имеет n входов данных, n выходов данных, m≤log2n битовых входов управляющего кода, вход тактовых импульсов и содержит входной регистр данных 1 с n входами данных, образующими входы данных устройства, входом тактовых импульсов, электрически соединенным с входом тактовых импульсов устройства.

Входной регистр n выходами данных электрически соединен с входами коммутационной матрицы, образованной переключателями Тij, где , , расположенными по n линиям и m уровням. Каждый переключатель матрицы имеет первый X1 и второй X2 входы данных, выход данных Y и битовый вход управляющего сигнала С, причем при подаче на битовый вход управляющего сигнала с низким логическим уровнем переключатель соединяет первый вход с выходом Y=X1, а при подаче на битовый вход управляющего сигнала с высоким логическим уровнем переключатель соединяет второй вход с выходом Y=X2. Под соединением входа и выхода понимается условие, при котором, если подать сигнал на вход, соединенный с выходом, на выходе через некоторую временную задержку, обусловленную временем распространения сигнала, появится входной сигнал. Матрица n выходами данных электрически соединена с входами данных выходного регистра данных 2, имеющего вход тактовых импульсов, который электрически соединен с входом тактовых импульсов устройства. Выходы данных выходного регистра образуют выходы данных устройства. Выходы переключателей первого уровня образуют выходы матрицы. Входы переключателей последнего уровня m образуют входы матрицы. Каждый выход QSi входного регистра данных электрически соединен с первым входом переключателя Tim уровня m и со вторым входом переключателя Тkm, причем k=i+2m-lmod(n), где 2m-lmod(n) - остаток от деления 2m-1 на n. Каждый выход переключателя Тil уровня 1<j<m электрически соединен с первым входом переключателя предыдущего уровня Tij-1 и со вторым входом переключателя предыдущего уровня Tkj-1, причем k=i+2j-lmod(n), где 2j-lmod(n) - остаток от деления 2j-1 на n. Каждый выход переключателя Тil первого уровня электрически соединен с входом данных DSi выходного регистра данных. Управляющие входы С переключателей первого уровня Тil электрически соединены между собой и с выходом S1 регистра кодов 3, управляющие входы С переключателей второго уровня Тi2 электрически соединены между собой и с выходом S2 регистра кодов и т.д., управляющие входы С переключателей уровня m Тim электрически соединены между собой и с выходом Sm регистра кодов. Входы битов кода управления С1, …, Сm образованы входами регистра кодов С1, …, Сm. Регистр кодов имеет вход тактовых импульсов, электрически соединенный с входом тактовых импульсов устройства. Число n>2 не обязательно является степенью числа 2. На фиг.3 приведена диаграмма орграфа, иллюстрирующая работу устройства для n=7.

Устройство работает следующим образом. На входы входного регистра данных через входы данных устройства подается строка данных, подлежащая операции циклического сдвига. Через входы битов кода управления сдвигом устройства на входы C1, C2, … Cm регистра кода подаются сигналы битов управляющего кода. По фронту управляющего импульса строка данных записывается во входной регистр данных, биты управляющего кода записываются в регистр кода и через время задержки, обусловленное распространением сигнала в коммутационной матрице, составляющее около τ·m, где τ - задержка на переключателе матрицы, сдвинутая строка данных поступает на входы DS1-DSn выходного регистра данных. На вход устройства подается новая строка данных, на входы C1, C2, … Cm подаются новые значения битов управляющего кода. По следующему фронту управляющего импульса новая строка данных записывается во входной регистр данных, новые биты управляющего кода записываются в регистр кода, а сдвинутая строка данных записывается в выходной регистр данных.

Таким образом, устройство выполняет циклический сдвиг входной строки данных на любое заданное битами управляющего кода число позиций, меньшее 2m, за один такт внешнего генератора тактовых импульсов. Время задержки преобразования сдвига составляет τ·m и не зависит от числа позиций, на которое осуществляется сдвиг. В обычном сдвиговом регистре для осуществления сдвига на 2m потребуется значительно большее время - примерно τ·2m. Аппаратная сложность устройства составляет 2 n-разрядных регистра, m разрядный регистр и не более n·log2n переключателей, число которых растет практически линейно с ростом n, что дает возможность реализовать устройство управляемого циклического сдвига для больших значений n.

Устройство управляемого циклического сдвига, характеризующееся наличием n входов данных, n выходов данных, m<log2n битовых входов управляющего кода и входа тактовых импульсов, входного регистра данных с n входами данных, образующими входы данных устройства, входом тактовых импульсов электрически соединенным с входом тактовых импульсов устройства, при этом входной регистр n выходами данных электрически соединен с входами коммутационной матрицы, образованной переключателями, расположенными по n линиям и m уровням и имеющими битовый вход управляющего сигнала, первый и второй входы данных и выход данных, причем при подаче на битовый вход управляющего сигнала с низким логическим уровнем переключатель соединяет первый вход с выходом, а при подаче на битовый вход управляющего сигнала с высоким логическим уровнем переключатель соединяет второй вход с выходом, матрица n выходами данных электрически соединена с входами данных выходного регистра данных, имеющего вход тактовых импульсов, который электрически соединен с входом тактовых импульсов устройства, выходы данных выходного регистра образуют выходы данных устройства, выходы переключателей первого уровня образуют выходы матрицы, входы переключателей последнего уровня m образуют входы матрицы, каждый выход с номером i входного регистра данных электрически соединен с первым входом переключателя с номером i уровня m и со вторым входом переключателя с номером k, причем k=i+2m-lmod(n), где 2m-lmod(n) - остаток от деления 2m-1 на n, каждый выход переключателя с номером i уровня l<j<m электрически соединен с первым входом переключателя с номером i предыдущего уровня j-1 и со вторым входом переключателя с номером k предыдущего уровня j-1, причем k=i+2j-1mod(n), где 2j-1mod(n) - остаток от деления 2j-1 на n, каждый выход переключателя с номером i первого уровня электрически соединен с входом данных с номером i выходного регистра данных, управляющие входы переключателей каждого уровня j электрически соединены между собой и с j-м выходом регистра кода, причем регистр кода имеет вход тактовых импульсов, электрически соединенный с входом тактовых импульсов устройства, и битовые входы управляющего кода устройства образованы m входами регистра кода.



 

Похожие патенты:

Изобретение относится к регистровым файлам, в частности к способам и системам для предоставления энергетически эффективных регистровых файлов. .

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

Изобретение относится к вычислительной технике. .

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

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

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

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

Изобретение относится к программируемому материалу памяти и к ячейке памяти, содержащей указанный материал памяти, в частности к тонкопленочной ячейке памяти. .

Изобретение относится к устройству обращения циклического сдвига и/или обращенного перемежения данных. .

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

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

Изобретение относится к возбуждающей схеме линий сигналов сканирования дисплейного устройства

Изобретение относится к вычислительной технике

Изобретение относится к вычислительной технике. Технический результат заключается в подавлении шумов каждого вывода разряда без увеличения размера схемы. Сдвиговый регистр содержит одну или более схем каскадного соединения, в каждой из которых разряды соединены друг с другом каскадом с обеспечением возможности передачи импульса сдвига, причем по меньшей мере одна из указанных одной или более схем каскадного соединения содержит в числе своих разрядов группу последовательных разрядов, а каждый разряд группы последовательных разрядов содержит первый выходной транзистор, второй выходной транзистор, первый конденсатор, второй конденсатор, входной вентиль, первый переключающий элемент, второй переключающий элемент, третий переключающий элемент, четвертый переключающий элемент и пятый переключающий элемент. 3 н. и 8 з.п. ф-лы, 16 ил.

Изобретения относятся к вычислительной технике и могут быть использованы в устройствах отображения. Техническим результатом является уменьшение размеров устройства. Триггер содержит первый (p-типа), второй (n-типа), третий (p-типа) и четвертый (p-типа) транзисторы; входные клеммы; первую и вторую выходные клеммы, первый и второй транзисторы составляют первую КМОП-схему, затворы транзисторов соединены один с другим и стоки транзисторов соединены один с другим, третий и четвертый транзисторы составляют вторую КМОП-схему, затворы транзисторов соединены один с другим и стоки транзисторов соединены один с другим, первая выходная клемма соединена с затворной стороной первой КМОП-схемы и стоковой стороной второй КМОП-схемы, вторая выходная клемма соединена с затворной стороной второй КМОП-схемы и стоковой стороной первой КМОП-схемы, по меньшей мере, один входной транзистор, включенный в группу указанных транзисторов с первого по четвертый, исток входного транзистора соединен с одной из входных клемм. 9 н. и 30 з.п. ф-лы, 75 ил.

Изобретение относится к вычислительной технике. Технический результат заключается в обеспечении реверсивности сдвига информации внутри сдвигового регистра. Сдвиговый регистр содержит ячейки, каждая из которых состоит из трех n-МОП транзисторов, двух емкостей, двух шин тактового питания, шины нулевого потенциала и их связей, причем в каждую ячейку дополнительно введены третья шина тактового питания, второй коммутирующий и второй нагрузочный n-МОП транзисторы, а также их связи. 2 ил.

Изобретение относится к оптоэлектронике и микроэлектронике и может быть использовано для построения сдвиговых регистров в фотоприемных субмодулях для мозаичных фотоприемников, в частности, в фотоприемниках на микроболометрах. Техническим результатом является обеспечение возможности двунаправленной передачи информации и минимизация занимаемой площади кристалла БИС. Устройство содержит ячейки, каждая из которых состоит из двух коммутирующих и информационного p-МОП транзисторов, p-МОП транзисторов управления нагрузкой, нагрузочного p-МОП транзистора, варактора, тактовых шин, шины нулевого потенциала, а также двух дополнительных p-МОП транзисторов управления нагрузкой в нечетной ячейке или второго варактора в четной ячейке. 3 ил.

Группа изобретений относится к оптоэлектронике и микроэлектронике и может быть использована для построения сдвиговых регистров в фотоприемных субмодулях для мозаичных фотоприемников, в частности, в фотоприемниках на микроболометрах. Техническим результатом является обеспечение двунаправленной передачи информации сдвигового регистра, повышение стабильности работы в условиях существенных паразитных емкостей тактовых шин, а также минимизация занимаемой площади кристалла интегральной схемы. Устройство содержит ячейки, каждая из которых состоит из коммутирующих и информационных МДП-транзисторов n-типа, коммутирующих и информационных МДП-транзисторов р-типа, шины питания, шины нулевого потенциала, тактовых шин. 3 н.п. ф-лы, 9 ил.

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