Устройство управляемой перестановки информации, хранимой в эвм
Владельцы патента RU 2405187:
Государственное образовательное учреждение высшего профессионального образования "Саратовский государственный университет им. Н.Г. Чернышевского" (RU)
Устройство относится к области преобразования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа. Техническим результатом является возможность высокоскоростного параллельного преобразования форматов блоков данных. Устройство управляемой перестановки информации, хранимой в ЭВМ, с n входами и n выходами управляющих кодов, n входами и n выходами данных включает в себя сортирующую сеть, каждая ячейка которой состоит из компаратора сортирующей сети, с двумя входами, двумя выходами и выходом управления, который соединен с входом управления транспозиционного элемента ячейки, имеющего два входа и два выхода данных, причем для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети, выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то вход транспозиционного элемента первой ячейки соединен с выходом транспозиционного элемента второй ячейки, входы управляющих кодов устройства образованы входами компараторов входных ячеек сортирующей сети, а выходы управляющих кодов устройства образованы выходами компараторов выходных ячеек сортирующей сети, входы данных образованы входами транспозиционных элементов выходных ячеек сортирующей сети, а выходы данных образованы выходами транспозиционных элементов входных ячеек сортирующей сети. 2 ил.
Устройство относится к области преобразования информации и может быть использовано в вычислительной технике, системах коммуникации и защиты информации от несанкционированного доступа.
Для задач, связанных с преобразованием форматов данных методом перестановок, необходимы высокоскоростные устройства, осуществляющие перестановку входных данных под управлением внешних кодов. Наибольший интерес представляют однотактные устройства, осуществляющие заданную перестановку за один такт внешнего генератора тактовых импульсов. В этом случае частое изменение управляющих кодов не должно приводить к замедлению работы устройства.
Известен дешифратор управляемой побитовой транспозиции информации, хранимой в персональной ЭВМ (см. патент РФ №2320000, МПК G06F 7/76). Дешифратор содержит К уровней узлов дешифрации, каждый уровень дешифрации содержит 2i элементов , регистр управляющих кодов, сдвиговый регистр данных, двойной буферный регистр накопления и хранения форматированных данных, блок управления, генератор тактовых импульсов. Вход выборки дешифратора соединен с первыми входами первого и второго элементов первого уровня. Элемент первого уровня реализует логическую функцию
, остальные элементы реализуют логическую функцию
. Вход Х элемента первого уровня соединен с выходом первого бита регистра управляющих кодов, входы X1 остальных элементов i-го уровня соединены с выходом i-ro бита регистра управляющих кодов, входы X2 остальных элементов i-ro уровня соединены с выходами элементов i-1 уровня, причем вход двойного буферного регистра накопления и хранения форматированных данных соединен с выходом сдвигового регистра данных, а входы разрешения записи этого регистра соединены с выходами последнего уровня дешифрации. Генератор тактовых импульсов соединен с блоком управления, который своими входами и выходами соединен с буферным регистром накопления и хранения форматированных данных, входным сдвиговым регистром данных, регистром управляющих кодов.
Недостатком данного дешифратора является последовательное преобразование данных, которое происходит за N тактовых импульсов генератора, что при больших значениях N значительно снижает быстродействие.
Известны сортирующие сети Бетчера ("Sorting Networks and Their Applications", К.E.Batcher, Proceedings of 1968 Spring Joint Computer Conference, pp.307-314, 1968). Данные устройства осуществляют быструю сортировку 2p элементов данных за 1/2р(1+р) шагов, но не обеспечивают перестановку данных, управляемую внешним кодом.
Известна модифицированная сеть Бетчера для сортировки несортированных входных сигналов за log2N последовательных проходов. Сеть строится рекурсивно от размера 4 до произвольного размера. Модифицированная сеть Бетчера сортирует N элементов данных за log2N последовательных проходов через сеть, где N - число элементов данных для каждого прохода. Сеть имеет задержку на log2N компараторах (см. патент US №5319788, МПК G06F 7/36; G06F 7/22).
Однако данная сеть не обеспечивает управляемую внешним кодом перестановку входных данных.
Известно устройство для осуществления управляемых перестановок, которое состоит из двух сетей типа «Butterfly» одинакового размера, соединенных одна с другой (back-to-back). Управление осуществляется программно с помощью процессора.
Недостатком данного устройства является программное управление перестановками, которое осуществляется процессором и приводит к замедлению работы системы (см. патент US №6922472, МПК H04L 9/34).
Задачей настоящего решения является упрощение и ускорение процесса управления перестановками при минимизации элементов устройства.
Техническим результатом является возможность высокоскоростного параллельного преобразования форматов блоков данных методом перестановок с использованием управляющих кодов.
Поставленная задача достигается тем, что устройство управляемой перестановки информации, хранимой в ЭВМ, с n входами и n выходами управляющих кодов, n входами и n выходами данных включает в себя сортирующую сеть, каждая ячейка которой состоит из компаратора сортирующей сети, с двумя входами, двумя выходами и выходом управления, который соединен с входом управления транспозиционного элемента ячейки, имеющего два входа и два выхода данных, причем для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети, выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то вход транспозиционного элемента первой ячейки соединен с выходом транспозиционного элемента второй ячейки, входы управляющих кодов устройства образованы входами компараторов входных ячеек сортирующей сети, а выходы управляющих кодов устройства образованы выходами компараторов выходных ячеек сортирующей сети, входы данных образованы входами транспозиционных элементов выходных ячеек сортирующей сети, а выходы данных образованы выходами транспозиционных элементов входных ячеек сортирующей сети.
Изобретение поясняется чертежами, где на фиг.1 приведена блок-схема устройства, на фиг.2 приведена схема для реализации управляемой перестановки вектора данных из 4 элементов на основе сортирующей сети Бетчера,
где
1. устройство управляемой перестановки;
2. ячейки сортирующей сети;
Х1, Х2,…, Хn - n входов данных;
Y1, Y2,…, Yn - n выходов данных;
IC1, IC2,…, IСn - n входов управляющих кодов;
ОС1, ОС2,…, ОСn-n выходов управляющих кодов;
π(1,2,…, n) - перестановка управляющих кодов;
(1,2,…, n) - отсортированные управляющие коды;
(x1, х2,…, хn) - входные данные;
π(х1, х2,…, хn) - выходные данные;
X1, X2 - первый и второй входы данных транспозиционных элементов;
Y1, Y2 - первый и второй выходы данных транспозиционных элементов;
IC1, IC2 - первый и второй входы компараторов;
OC1, OC2 - первый и второй выходы компараторов;
IC1, IC2, IC3, IC4 - входы управляющих кодов;
OC1, OC2, ОС3, ОС4 - выходы управляющих кодов;
X1, Х2, Х3, Х4 - входы данных;
Y1, Y2, Y3, Y4 - выходы данных.
Предлагаемое устройство включает в себя сортирующую сеть 1, в узлах которой находятся ячейки 2, состоящие из компаратора сортирующей сети и транспозиционного элемента управляемой перестановки данных. Компаратор сортирующей сети имеет управляющий выход (на чертежах не показан), два входа IC1, IC2 и два выхода OC1, OC2. Транспозиционный элемент имеет вход управления, входы X1, Х2 и выходы Y1, Y2. В каждой ячейке управляющий выход компаратора соединен с входом управления транспозиционного элемента.
Соединения выходов OC1 и входов IC1, выходов ОС2 и входов IC2 компараторов определяются топологией используемой сортирующей сети. Соединения IC1,IC2,…, ICn входов управляющих кодов с входами компараторов входных ячеек сортирующей сети определяются топологией используемой сортирующей сети. Соединения ОС1,ОС2,…, ОСn выходов управляющих кодов с выходами компараторов выходных ячеек сортирующей сети определяются топологией используемой сортирующей сети.
Если выход ОС1 компаратора одной ячейки сортирующей сети соединен с входом IC1 компаратора другой ячейки сортирующей сети, то вход X1 транспозиционного элемента одной ячейки соединен с выходом Y1 другой ячейки. Если выход ОС2 компаратора одной ячейки сортирующей сети соединен с входом IC2 компаратора другой ячейки сортирующей сети, то вход Х2 транспозиционного элемента одной ячейки соединен с выходом Y2 другой ячейки. Если выходы OC1, OC2 выходной ячейки сортирующей сети являются выходами управляющих кодов устройства, то входы X1, Х2 транспозиционного элемента этой ячейки являются входами данных. Если входы IC1, IС2 входной ячейки сортирующей сети являются входами управляющих кодов устройства, то выходы Y1, Y2 транспозиционного элемента этой ячейки являются выходами данных.
Устройство работает следующим образом. На n входов управляющих кодов IC1,IC2,…, ICn, образованных входами компараторов IС1, IС2 устройства, подаются входные управляющие коды, представляющие собой перестановку чисел натурального ряда π(1,2,…, n). На n входов данных Х1,Х2,…, Хn, образованных входами транспозиционных элементов Х1, Х2 устройства, подаются входные данные (x1,x2,…, xn). Через время задержки τ, на n выходах данных Y1,Y2,…, Yn, образованных выходами транспозиционных элементов устройства, появляются выходные данные, представляющие собой перестановку π(х1,х2,…, хn). Время задержки τ определяется количеством элементов на пути распространения сигналов управления и данных. Если значение кода на входе компаратора IC1 больше или равно значения кода на входе компаратора IC2, то значение кода поступает с входа IC1 на выход OC1, а значение кода на входе IC2 поступает на выход ОС2. Одновременно на управляющем выходе компаратора появляется сигнал, который подается на управляющий вход транспозиционного элемента. При этом перестанавливаемые данные на входе X1 поступают на выход Y1; а перестанавливаемые данные на входе Х2 поступают на выход Y2.
Если значение кода на входе компаратора IС1 меньше значения кода на входе компаратора IC2, то значение кода поступает с входа IC1 на выход ОС2, а значение кода на входе IC2 поступает на выход OC1. Одновременно на управляющем выходе компаратора появляется сигнал, который подается на управляющий вход транспозиционного элемента. При этом перестанавливаемые данные на входе X1 поступают на выход Y2; а перестанавливаемые данные на входе Х2 поступают на выход Y1.
Таким образом, перестановка входного вектора данных (х1,х2,…, хn) в соответствии с входными управляющими кодами π(1,2,…, n) выполняется параллельно, что обеспечивает высокую скорость преобразования. Число ячеек устройства зависит от топологии используемой сортирующей сети и для сетей Бетчера составляет O(n·(log2 n)2). Это число растет практически линейно с ростом n, что делает технически возможным управляемую перестановку больших блоков данных.
Устройство управляемой перестановки информации, хранимой в ЭВМ, с n входами и n выходами управляющих кодов, n входами и n выходами данных, включает в себя сортирующую сеть, каждая ячейка которой состоит из компаратора сортирующей сети, с двумя входами, двумя выходами и выходом управления, который соединен с входом управления транспозиционного элемента ячейки, имеющего два входа и два выхода данных, причем для пар ячеек, компараторы которых соединены между собой в соответствии с топологией сортирующей сети, выполняется условие, если выход компаратора первой ячейки соединен с входом компаратора второй ячейки, то вход транспозиционного элемента первой ячейки соединен с выходом транспозиционного элемента второй ячейки, входы управляющих кодов устройства образованы входами компараторов входных ячеек сортирующей сети, а выходы управляющих кодов устройства образованы выходами компараторов выходных ячеек сортирующей сети, входы данных образованы входами транспозиционных элементов выходных ячеек сортирующей сети, а выходы данных образованы выходами транспозиционных элементов входных ячеек сортирующей сети.