УСТРОЙСТВО КРОСС-КЛАСТЕРНОЙ УПРАВЛЯЕМОЙ ПЕРЕСТАНОВКИ ИНФОРМАЦИИ, ХРАНИМОЙ В ПЕРСОНАЛЬНОЙ ЭВМ Российский патент 2011 года по МПК G06F12/14 G06F17/20 

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

Известно устройство для осуществления перестановок с использованием команд, основанное на сетях «butterfly» (см. патент US №6922472, МПК H04L 9/34). Используя данное устройство, можно осуществлять кросс-кластерные перестановки входных данных.

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

Известно устройство для осуществления перестановок с использованием команд основанных на базе сетей омега (omega) и флип (flip) (см. патент US №6952478, МПК G06F7/76; G06F 9/30). Предложены инструкции для осуществления перестановок, которые могут использоваться в программном обеспечении, выполненном в программируемом процессоре. Инструкции для осуществления перестановок основаны на сети омега-флип, включающей, по крайней мере, два уровня, каждый из которых может выполнить функцию или сети омега или флип. Начальная последовательность битов от исходного регистра преобразуется в промежуточные последовательности битов. Каждая промежуточная последовательность битов является входной для последующей инструкции перестановки. Инструкции перестановки определены для того, чтобы переставить начальную исходную последовательность битов в одну или более промежуточных последовательностей битов, пока не будет получена требуемая перестановка. Промежуточные последовательности битов определены битами конфигурации. Инструкции перестановки образуют последовательность инструкций перестановки, состоящую, по крайней мере, из одной инструкции. Последовательность инструкций перестановки максимального размера составляет 21r/m инструкций перестановки, где r - число переставляемых k-битных элементов, m - число уровней сети, задействованных в одной инструкции. Инструкции перестановки могут использоваться, чтобы переставить k-битные элементы, упакованные в n-битное слово, где k может быть 1,2…, n, и k*r=n.

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

Наиболее близким к заявляемому решению является дешифратор управляемой побитовой транспозиции информации, хранимой в персональной ЭВМ (см. патент РФ №2320000, МПК G06F 7/76). Дешифратор содержит К уровней узлов дешифрации, каждый уровень дешифрации содержит 2ⁱ элементов , регистр управляющих кодов, сдвиговый регистр данных, двойной буферный регистр накопления и хранения форматированных данных, блок управления, генератор тактовых импульсов. Вход выборки дешифратора соединен с первыми входами первого и второго элементов первого уровня. Элемент первого уровня реализует логическую функцию Y₁=X,Y₂=, остальные элементы реализуют логическую функцию Y₁= ₁×Х₂,У₂=Х₁×Х₂. Вход Х элемента первого уровня соединен с выходом первого бита регистра управляющих кодов, входы X₁ остальных элементов i-того уровня соединены с выходом i-го бита регистра управляющих кодов, входы Х₂ остальных элементов i-го уровня соединены с выходами элементов i-1 уровня, причем вход двойного буферного регистра накопления и хранения форматированных данных соединен с выходом сдвигового регистра данных, а входы разрешения записи этого регистра соединены с выходами последнего уровня дешифрации. Генератор тактовых импульсов соединен с блоком управления, который своими входами и выходами соединен с буферным регистром накопления и хранения форматированных данных, входным сдвиговым регистром данных, регистром управляющих кодов.

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

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

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

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

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

1 - дешифратор;

2 - регистр управляющих кодов;

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

4 - выходной регистр данных первого кластера;

5 - выходной регистр данных второго кластера;

X1,…,Xn - n входов элементов данных устройства;

Y1,…,,Yn/2 - n/2 выходов элементов данных первого кластера;

Yn/2+l,...,Yn - n/2 выходов элементов данных второго кластера;

С1,…,Cm - m входов управляющих битов;

F₁,…,F₃ - уровни дешифрации;

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

Х₁ Х₂ - первый и второй входы управляемого и неуправляемого

транспозиционного элемента;

Y₁, Y₂ - первый и второй выходы управляемого и неуправляемого

транспозиционного элемента;

COD - вход управляющего кода управляемого транспозиционного элемента.

Предлагаемое устройство управляемой кросс-кластерной перестановки информации состоит из дешифратора 1, входы управляющих кодов которого соединены с выходами регистра управляющих кодов 2. Входы регистра управляющих кодов 2 образуют входы управляющих кодов устройства. Входы данных дешифратора 1 соединены с выходами n=2^k - разрядного входного регистра данных 3, входы которого образуют входы данных устройства. Выходы данных дешифратора 1 соединены с входами данных n/2-разрядных выходных регистров данных первого и второго кластеров 4 и 5, выходы которых образуют выходы данных устройства. Регистр управляющих кодов 2, выходные регистры первого и второго кластеров 4 и 5, входной регистр данных 3 имеют входы для подключения к внешнему источнику тактовых импульсов. Дешифратор 1 состоит из управляемых и неуправляемых транспозиционных элементов T_ij, где с двумя входами Х_1, Х₂, двумя выходами Y₁, Y₂, причем управляемые транспозиционные элементы имеют также вход управляющего кода COD, который принимает значения логического нуля или единицы.

Управляемые и неуправляемые транспозиционные элементы дешифратора 1 образуют матрицу с n-линиями и k уровнями F_l,…F_k. Входы управляющих кодов дешифратора 1 образованы входами кодов транспозиционных элементов COD. Входы данных дешифратора 1 образованы входами транспозиционных элементов первого уровня Т_i1. Каждый транспозиционный элемент T_im уровня своими выходами соединен с входами данных транспозиционных элементов T_{hm+l, Tpm+l} уровня m+1, причем

где int - функция выделения целой части, (j+2^k-m-l-1)modn - операция вычисления остатка от частного Транспозиционные элементы всех уровней разбиты на группы, номер группы d определяется выражением один из транспозиционных элементов T_im уровня m, относящийся к одной группе d, является неуправляемым.

На фиг.2 управляющие входы транспозиционных входов COD не показаны.

Каждый вход транспозиционных элементов m+1 уровня соединен с одним выходом транспозиционных элементов m уровня. Каждый выход транспозиционных элементов m уровня соединен с одним входом транспозиционных элементов m+1 уровня. Один выход транспозиционных элементов k-го уровня соединен с одним из входов выходного регистра данных первого кластера. Второй выход транспозиционных элементов k-го уровня соединен с одним из входов выходного регистра данных второго кластера.

Устройство работает следующим образом.

Перед началом преобразования по переднему фронту тактового импульса clk в регистр управляющих кодов 2 записываются управляющие коды, в регистр данных 3 записывается n элементов данных. Каждый бит управляющих кодов, записанный в регистр управляющих кодов 2, подается на вход COD одного из транспозиционных элементов дешифратора 1. Если значение на входе COD транспозиционного элемента имеет высокий логический уровень, то переставляемый элемент данных с входа X₁ поступает на выход Y₂, а со входа Х₂ на выход Y₂, осуществляя, таким образом, операцию транспозиции входных элементов данных. Если значение на входе COD транспозиционного элемента имеет низкий логический уровень, то переставляемый элемент данных с входа X₁ поступает на выход Y₁, а с входа Х₂ на выход Y₂. По переднему фронту следующего тактового импульса перестановленные элементы данных записываются в выходные регистры первого и второго кластеров 4 и 5. Одновременно в регистр управляющих кодов 2 записываются новые управляющие коды, а в регистр данных 3 записывается n следующих элементов данных.

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

Число логических элементов дешифратора n/2·log₂n растет практически линейно с ростом N, что делает технически возможным кросс-кластерную перестановку больших блоков данных. Число различных кросс-кластерных перестановок, осуществляемых данным устройством

Комбинирование одного устройства для кросс-кластерной перестановки n элементов входных данных с двумя устройствами кросс-кластерной перестановки n/2 элементов входных данных позволяет осуществить любую перестановку между четырьмя кластерами размером n/4 элементов. При этом устройства кросс-кластерной перестановки n/2 элементов соединяются своими входами с выходами первого и второго кластеров 4 и 5 устройства кросс-кластерной перестановки n элементов. Промежуточные входные и выходные регистры данных можно удалить из системы. Число различных кросс-кластерных перестановок, осуществляемых комбинированным устройством в данном случае, будет . Использование различных вариантов последовательного включения кросс-кластерной перестановки с удалением промежуточных входных и выходных регистров данных дает возможность реализовать любую перестановку между кластерами, размером 2^m, где . Если для любого кластера m=1 реализуется любая перестановка входных данных из n! вариантов.

Данное устройство можно использовать для осуществления перестановок мультимножеств (множеств с повторяющимися элементами).

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

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

1. Устройство кросс-кластерной управляемой перестановки информации, хранимой в персональной ЭВМ, включающее дешифратор, входы управляющих кодов которого соединены с выходами регистра управляющих кодов, входы которого образуют входы управляющих кодов устройства, входы данных дешифратора соединены с выходами n=2^k-разрядного входного регистра данных, входы которого образуют входы данных устройства, выходы данных дешифратора соединены с входами данных n/2-разрядных выходных регистров первого и второго кластеров, выходы которых образуют выходы данных устройства, при этом регистр управляющих кодов, выходные регистры первого и второго кластеров, регистр входных данных имеют входы для подключения к внешнему источнику тактовых импульсов, причем дешифратор состоит из управляемых и неуправляемых транспозиционных элементов Т_ij, где , с двумя входами X₁, X₂, двумя выходами Y₁, Y₂, причем управляемые транспозиционные элементы имеют также вход управляющего кода COD, который принимает значения логического нуля или единицы.

2. Устройство по п.1, отличающееся тем, что входы управляющих кодов дешифратора образованы входами кодов транспозиционных элементов, входы данных дешифратора образованы входами транспозиционных элементов первого уровня Т_j1.

3. Устройство по п.1, отличающееся тем, что входы выходного регистра данных первого кластера соединены с одним из выходов транспозиционных элементов k уровня, входы выходного регистра данных второго кластера соединены со вторым из выходов транспозиционных элементов k уровня.

4. Устройство по п.1, отличающееся тем, что каждый вход транспозиционных элементов m+1 уровня соединен с одним выходом транспозиционных элементов уровня m.

5. Устройство по п.1, отличающееся тем, что каждый транспозиционный
элемент Т_im уровня своими выходами соединен с входами данных транспозиционных элементов T_hm+1, T_pm+1 уровня m+1, причем
,
, один из транспозиционных элементов T_im уровня m, относящихся к одной группе d, номер которой определяется выражением , является неуправляемьм, где int - функция выделения целой части, (j+2^k-m-l-1)modn - операция вычисления остатка от частного .