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

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

Иллюстрации

Показать все

Реферат

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

Известен реверсивный регистр сдвига (далее объект), приведенный в книге С.А.Майорова и Г.И.Новикова Принципы организации цифровых машин, изд. «Машиностроение», Ленинград 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, … 2^k-1. Дешифратор для конкретного значения управляющего кода вырабатывает единичный сигнал только на одном управляющем выходе дешифратора (например, с номером s=u₁+2u₂…+2^m-1u_m), поэтому значения на выходе блока циклического сдвига имеют вид: bj=a_{(s+j)mod n}r_s=a_{(j+s)mod n} или b_j=a_i, где j=(i-r)modn и r=s. Сложность реализации схемы оценивается количеством используемых ключей, которое равно n². Главным достоинством данного решения является выполнение операции циклического сдвига с постоянным временем задержки (один такт), независимо от разрядности информационного блока. Заметим, что задержка в дешифраторе, связанная с формированием управляющих сигналов, зависит от конкретной реализации схемы блока управляемых перестановок. В большинстве случаев можно осуществить одновременное поступление управляющих сигналов на все дешифраторы и, следовательно, в этом случае время задержки не зависит от числа уровней.

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

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

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

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

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

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

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

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

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

- Т₁₁, Т₂₁ Т₃₁, T₄₁, T₅₁, Т₆₁, T₇₁, T₈₁ - переключатели первого уровня коммутационной матрицы;

- T₁₂, T₂₂, Т₃₂, Т₄₂, Т₅₂, Т₆₂, Т₇₂, T₈₂ - переключатели второго уровня коммутационной матрицы;

- T₁₃, Т₂₃, Т₃₃, Т₄₃, Т₅₃, Т₆₃, Т₇₃, Т₈₃ - переключатели третьего уровня коммутационной матрицы;

- 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≤log₂n битовых входов управляющего кода, вход тактовых импульсов и содержит входной регистр данных 1 с n входами данных, образующими входы данных устройства, входом тактовых импульсов, электрически соединенным с входом тактовых импульсов устройства.

Входной регистр n выходами данных электрически соединен с входами коммутационной матрицы, образованной переключателями Т_ij, где , , расположенными по n линиям и m уровням. Каждый переключатель матрицы имеет первый X1 и второй X2 входы данных, выход данных Y и битовый вход управляющего сигнала С, причем при подаче на битовый вход управляющего сигнала с низким логическим уровнем переключатель соединяет первый вход с выходом Y=X1, а при подаче на битовый вход управляющего сигнала с высоким логическим уровнем переключатель соединяет второй вход с выходом Y=X2. Под соединением входа и выхода понимается условие, при котором, если подать сигнал на вход, соединенный с выходом, на выходе через некоторую временную задержку, обусловленную временем распространения сигнала, появится входной сигнал. Матрица n выходами данных электрически соединена с входами данных выходного регистра данных 2, имеющего вход тактовых импульсов, который электрически соединен с входом тактовых импульсов устройства. Выходы данных выходного регистра образуют выходы данных устройства. Выходы переключателей первого уровня образуют выходы матрицы. Входы переключателей последнего уровня m образуют входы матрицы. Каждый выход QS_i входного регистра данных электрически соединен с первым входом переключателя T_im уровня m и со вторым входом переключателя Т_km, причем k=i+2^m-lmod(n), где 2^m-lmod(n) - остаток от деления 2^m-1 на n. Каждый выход переключателя Т_il уровня 1<j<m электрически соединен с первым входом переключателя предыдущего уровня T_ij-1 и со вторым входом переключателя предыдущего уровня T_kj-1, причем k=i+2^j-lmod(n), где 2^j-lmod(n) - остаток от деления 2^j-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 подаются новые значения битов управляющего кода. По следующему фронту управляющего импульса новая строка данных записывается во входной регистр данных, новые биты управляющего кода записываются в регистр кода, а сдвинутая строка данных записывается в выходной регистр данных.

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

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