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

Классы МПК:G11C19/00 Цифровые запоминающие устройства со ступенчатым движением информации, например сдвиговые регистры
Автор(ы):, ,
Патентообладатель(и):Государственное образовательное учреждение высшего профессионального образования "Саратовский государственный университет им. Н.Г. Чернышевского" (RU)
Приоритеты:
подача заявки:
2009-09-14
публикация патента:

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

устройство управляемого циклического сдвига, патент № 2419174 устройство управляемого циклического сдвига, патент № 2419174 устройство управляемого циклического сдвига, патент № 2419174

Формула изобретения

Устройство управляемого циклического сдвига, характеризующееся наличием n входов данных, n выходов данных, m<log2 n битовых входов управляющего кода и входа тактовых импульсов, входного регистра данных с 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 входами регистра кода.

Описание изобретения к патенту

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Поставленная задача достигается тем, что устройство управляемого циклического сдвига согласно изобретению содержит n входов данных, n выходов данных, mустройство управляемого циклического сдвига, патент № 2419174 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, T 22, Т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устройство управляемого циклического сдвига, патент № 2419174 log2n битовых входов управляющего кода, вход тактовых импульсов и содержит входной регистр данных 1 с n входами данных, образующими входы данных устройства, входом тактовых импульсов, электрически соединенным с входом тактовых импульсов устройства.

Входной регистр n выходами данных электрически соединен с входами коммутационной матрицы, образованной переключателями Тij, где устройство управляемого циклического сдвига, патент № 2419174 , устройство управляемого циклического сдвига, патент № 2419174 , расположенными по n линиям и m уровням. Каждый переключатель матрицы имеет первый X1 и второй X2 входы данных, выход данных Y и битовый вход управляющего сигнала С, причем при подаче на битовый вход управляющего сигнала с низким логическим уровнем переключатель соединяет первый вход с выходом Y=X1, а при подаче на битовый вход управляющего сигнала с высоким логическим уровнем переключатель соединяет второй вход с выходом Y=X2. Под соединением входа и выхода понимается условие, при котором, если подать сигнал на вход, соединенный с выходом, на выходе через некоторую временную задержку, обусловленную временем распространения сигнала, появится входной сигнал. Матрица n выходами данных электрически соединена с входами данных выходного регистра данных 2, имеющего вход тактовых импульсов, который электрически соединен с входом тактовых импульсов устройства. Выходы данных выходного регистра образуют выходы данных устройства. Выходы переключателей первого уровня образуют выходы матрицы. Входы переключателей последнего уровня m образуют входы матрицы. Каждый выход QSi входного регистра данных электрически соединен с первым входом переключателя T im уровня 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, устройство управляемого циклического сдвига, патент № 2419174 , Сm образованы входами регистра кодов С1, устройство управляемого циклического сдвига, патент № 2419174 , Сm. Регистр кодов имеет вход тактовых импульсов, электрически соединенный с входом тактовых импульсов устройства. Число n>2 не обязательно является степенью числа 2. На фиг.3 приведена диаграмма орграфа, иллюстрирующая работу устройства для n=7.

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

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

Класс G11C19/00 Цифровые запоминающие устройства со ступенчатым движением информации, например сдвиговые регистры

сдвиговый регистр -  патент 2527188 (27.08.2014)
сдвиговый регистр -  патент 2522306 (10.07.2014)
триггер, регистр сдвига, схема возбуждения устройства отображения, устройство отображения и панель устройства отображения -  патент 2507680 (20.02.2014)
сдвиговый регистр и дисплейное устройство -  патент 2493621 (20.09.2013)
сдвиговый регистр, устройство отображения, снабженное таковым, и способ возбуждения сдвигового регистра -  патент 2488180 (20.07.2013)
резервированный регистр в многофазном коде -  патент 2486611 (27.06.2013)
дисплейное устройство и способ для возбуждения дисплейного устройства -  патент 2452038 (27.05.2012)
способ записи и воспроизведения разноскоростных цифровых потоков на носители информации -  патент 2427932 (27.08.2011)
способ и система для предоставления энергетически эффективного регистрового файла -  патент 2400804 (27.09.2010)
динамическое последовательное функциональное устройство -  патент 2392672 (20.06.2010)
Наверх